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