c언어 3190번 뱀 (백준)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 

bool map[101][101] = {0}; //사과의 존재유무
int exist[101][101] = {}; //뱀이 있는 공간

typedef struct Node{
	struct Node *next;
	int y;
	int x;
}Node; 

typedef struct Queue{
	Node *front;
	Node *rear;
	int count;
}Queue;

void queue_init(Queue *queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
	return;
}

int queue_empty(Queue *queue) {
	return queue->count == 0;
}

void queue_push(Queue *queue, int y, int x) {
	Node *newNode = (Node*) malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->y = y;
	newNode->x = x;
	exist[y][x]++;
	
	if(queue_empty(queue)) queue->front = newNode;
	else queue->rear->next = newNode;
	queue->rear = newNode;
	queue->count++;
	return;
}

void queue_pop(Queue *queue) {
	Node *ptr = queue->front;
	queue->front = ptr->next;
	exist[ptr->y][ptr->x]--;
	free(ptr);
	queue->count--;
	return;
}

int main(void) 
{
	Queue queue;
	queue_init(&queue);
	
	int n = 0;
	int apple = 0;
	scanf("%d", &n);
	scanf("%d", &apple);
	
	while(apple--) { //사과
		int y, x;
		scanf("%d %d", &y, &x);
		map[y][x] = true;
	}
	
	int m = 0;
	scanf("%d", &m);
	int turn[m][2]; //몇초에 어디로 틀지를 담을 배열
	int turn_ptr = 0;

	for(int i=0; i<m; i++) { //방향
		char tmp = 0;
		scanf("%d %c", &turn[i][0], &tmp);
		if(tmp == 'D') turn[i][1] = 1; //right
		else turn[i][1] = 0; //left
	}
	
	int y=1, x=1; //처음엔 1, 1에서만 존재한다.
	queue_push(&queue, y, x);
    
	int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //방향을 담은 배열
	int di = 0;
	int i = 0;
	for(i=0; ;i++) {
		if(i==turn[turn_ptr][0] && turn_ptr < m) { //방향 전환
			if(turn[turn_ptr][1]) di++; //오른쪽
			else di--; //왼쪽
			if(di > 3) di = 0;
			if(di < 0) di = 3; 
			turn_ptr++;
		}
		//한 칸 움직이기
		y+=direction[di][0]; 
		x+=direction[di][1];
		queue_push(&queue, y, x); //한 칸 생성
		
		if(exist[y][x]>1) break; //만약 머리와 머리 외 부분이 만났다면 반복문 종료
		
		if(y<1 || y>n || x<1 || x>n) { //만약 머리가 범위를 벗어났다면 반복문 종료
			break;
		}
		
		if(map[y][x] == true) map[y][x] = false; //머리가 있는 부분에 사과가 있다면 맨 뒤가 사라지지 않음
		else queue_pop(&queue); //맨 뒤부분 삭제
	}
	printf("%d", i+1); //걸린 시간 출력
	return 0;
}

 

풀이 : 큐를 만든 다음에, 큐를 생성하고,  제거하면서, 머리가 범위를 초과하거나, 다른 큐의 노드와 중첩되면 멈추도록 만들었다.

 

1. 큐를 만듦, 사과의 위치와 존재유무를 담을 배열을 만듦, 뱀의 요소가 있는 곳을 담을 배열을 만듦

2. 맵의 크기를 입력 받음

3. 사과의 개수와 위치를 입력 받음

4. 초와 그 때의 방향 전환 에 대한 데이터를 입력 받음

5. 반복문을 돌리면서, 방향을 바꿀 수 있으면, 방향을 바꾼 다음, 머리를 생성하고, 꼬리를 제거한다.

6. 단 꼬리를 제거하지 전에 머리가 범위를 벗어나거나, 이미 생성된 곳과 겹쳤으면 반복문을 종료함

7. 6. 이후, 단 머리가 사과가 있는 곳에 생성되면 꼬리를 제거하지 않음

8. 걸린 시간을 출력함

 

 

 

범위가 한정되어 있고, 또한 크지 않다보니, 노드를 만들어서 크기가 가변적인 큐를 이용하는 것 보다, 그냥 배열을 통해 큐를 구현해서 푸는 것이 더욱더 쉽고, 빠르고 간단하게 만들고 풀 수 있다고 생각한다.

 

https://www.acmicpc.net/problem/3190

3190번: 뱀