c언어 14940번 쉬운 최단거리 (백준)

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

short int map[1000][1000] = {}; //map
char visited[1000][1000] = {}; //방문?
int n, m;

typedef struct Node { //큐에 넣을 노드
	int i, j, v;
	struct Node * next;
}Node;

typedef struct Queue{ //큐
	Node *front;
	Node *back;
	int cnt;
}Queue;

void push(Queue* q, int i, int j, int v) { //넣기
	++(q->cnt);
	Node * node = (Node*) malloc(sizeof(Node));
	node->i = i;
	node->j = j;
	node->v = v;
	node->next = NULL;
	
	if(q->front == NULL) q->front = q->back = node; //아무것도 없을때
	else {
		q->back->next = node;
		q->back = node;
	}
	return;
}

Node* pop(Queue* q) { //꺼내기
	--(q->cnt);
	Node* p = q->front;
	q->front = p->next;
	
	if(q->front == NULL) q->back = NULL; //전부다 꺼냈을 때
	return p;
}


int main(void)
{
	int a, b, tmp;
	scanf("%d %d", &n, &m);
	
    //큐 초기화
	Queue q;
	q.cnt = 0;
	q.front = q.back = NULL;
	
	for(int i=0; i<n; i++) { //데이터 입력
		for(int j=0; j<m; j++) {
			scanf("%d",&tmp);
			map[i][j] = tmp;
			if(tmp == 2) { //목적지는 따로 저장
				a = i;
				b = j;
			}
		}
	}
	
	visited[a][b] = 1; //넣기전에 방문처리
	push(&q, a, b, 0); //목적지를 큐에
	
	while(q.cnt>0) { //큐가 빌 때까지
		
		Node* node = pop(&q);
		int i = node->i;
		int j = node->j;
		int v = node->v;
        
		if(map[i][j] > 0) { //DFS
			map[i][j] = v++;
			if(i>0 && visited[i-1][j]++ == 0) push(&q, i-1, j, v);
			if(i<n-1 && visited[i+1][j]++ == 0) push(&q, i+1, j, v);
			if(j>0 && visited[i][j-1]++ == 0) push(&q, i, j-1, v);
			if(j<m-1 && visited[i][j+1]++ == 0) push(&q, i, j+1, v);
		}
		free(node); //큐에 넣기위해 동적할당했던 메모리를 다시 해제
	}
	
	for(int i=0; i<n; i++) { //출력
		for(int j=0; j<m; j++) {
			if(!visited[i][j] && map[i][j] == 1) map[i][j] = -1; //만약 1이고, 방문할 수 없었다면
			printf("%hd ", map[i][j]);
		} printf("\n");
	}
}

풀이 : DFS

 

주의할 점은 DFS에서 한번 확인한 곳은 다시 큐에 집어 넣어서는 안되는데

이 때, pop 한 다음에 중복 방지를 위한 값을 바꿔주면, 이전에 같은 값들이 여러번, 수만번 큐에 들어가기에 시간초과가 됩니다.

 

즉 반드시 DFS에서 중복 방지를 위한 값은 큐에 넣기전이나, 넣은 후 바로 바꾸어 주어야 합니다. 이래야 같은 데이터가 큐에 중복으로 들어가지 않습니다.

 

또한 큐에서 꺼낸 데이터는 동적할당 해주어야 합니다.

 

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

14940번: 쉬운 최단거리