[백준] 미로 탐색 (BFS)

 

 

 

이번 문제는 BFS를 응용한 길찾기 문제에 대해 알아보자.

 

백준 2178번 문제

 

보통 미로 찾기 문제를 풀 때 BFS를 사용하는 이유는 DFS의 경우 도착지에 도달하지 못하는 경우, 무한 루프에 빠지지만 BFS는 큐의 아이템이 모두 빠져나가면 루프를 종료하기 때문에 도착 여부를 체크 할 수 있기 때문이다.

 

#include <stdio.h>
#define MAX 101
#define INFI 999999
int Map[MAX][MAX];

typedef struct Queue {
	int x;
	int y;
	int s;
} Queue;

Queue Q[INFI];
int front = -1, rear = -1;

void DFS (int maxY, int maxX) {
	// 왼, 오, 위, 아
	int directX[] = {-1, 1, 0, 0};
	int directY[] = {0, 0, -1, 1};
	
	// 시작 지점 초기화
	rear++;
	Q[rear].x = 0;
	Q[rear].y = 0;
	Q[rear].s = 1;
	
	// 시작 지점 방문표시
	Map[0][0] = 0;
	
	// 너비 우선 탐색 시작
	while (front < rear) {
		front++;
		int x = Q[front].x;
		int y = Q[front].y;
		int s = Q[front].s;
		
		// 도착 지점에 온 경우
		if (x == maxX - 1 && y == maxY - 1) {
			printf("%d\n", s);
			return;
		}
		
		// 4방향 체크 시작
		for (int i = 0; i < 4; i++) {
			// 이동 좌표 계산
			int nextX = directX[i] + x;
			int nextY = directY[i] + y;
			
			// 이동 좌표 유효성 검사
			if (nextX < 0 || nextX >= maxX || nextY < 0 || nextY >= maxY) {
				continue;
			}
			
			// 현재 맵에서 이동 가능한지?
			if (Map[nextY][nextX] == 1) {
				// 큐에 추가
				rear++;
				Q[rear].x = nextX;
				Q[rear].y = nextY;
				Q[rear].s = s + 1;
				
				// 방문 표시
				Map[nextY][nextX] = 0;
			}
		}
	}
}

int main(void) {
	int N = 0, M = 0;
	
	scanf("%d %d", &N, &M);
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			scanf("%1d", &Map[y][x]);
		}
	}
	
	if (Map[0][0] == 1) {
		DFS(N, M);
	} else {
		printf("0\n");
	}
	
	return 0;
}

 

이번 문제에서 주의해야 할 점은 이전 게시글의 문제들과 달리, 결과 값을 전역이 아닌 큐에 저장하고 도착 지점에 도달하면 큐에 저장된 결괏값을 출력하는 것이다. 왜 큐에 결과값을 개별로 저장해야 하는지 알아보자.

 

 

결과값을 큐에 저장해야 하는 이유

 

예제의 입력 값은 아래와 같다.

4 6
101111
101010
101011
111011

 

BFS로 이동할 때 좌표와 사이즈를 출력해보자.

 

예제 입력값에 대한 BFS 이동

출력값을 자세히 보면 (4, 0)에서 길이 나눠지는 것을 볼 수 있다. 이때, 결과 값을 전역 변수로 저장하면 이동 가능한 칸을 모두 더하기 때문에 17이 출력된다. 하지만 문제에서 원하는 것은 도착 지점에서의 최소 이동 칸의 개수이기 때문에 결괏값을 전역 변수로 선언하면 안 된다.

 

큐에 결과 값을 저장하면 좌표마다 이동했던 칸의 갯수가 개별로 저장된다. 따라서, (4, 0)에서 길이 나눠지더라도 도착 지점의 이동 칸수에는 반영되지 않는다. 좌표 (4, 2)에도 분기가 있지만 도착 지점에는 반영되지 않았음을 확인 할 수 있다.