BOJ 2178 : 미로 탐색

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2178

 

 

BFS를 이용하여 MAP에 거리를 남길 수 있다.

이 문제의 경우는 벽이 0, 길이 1이므로, 1인 경우에 큐에 담고, visit을 체크한다.

 

다음과 같은 미로가 있다고 가정하자.

 

우리가 최종적으로 구해야할 지도의 모습은 아래와 같다.

 

도착점부터 칸을 세기 때문에 (1, 1)에서 (5, 5)까지 이동해야하는 칸은 총 9칸이다.

 

이제 BFS를 이용하여 거리를 재보자.

2차원 MAP 탐색의 기본은 단지번호붙이기와 비슷하다.

지금의 경우는 큐에서 pop할 때마다, 현재 위치 + 1을 기록하면 된다.

 

※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다.

---

먼저 최초 시작점 (1, 1)을 queue에 담고, visit[1][1] = 1로 체크하자.

void BFS(int r, int c)
{
	wp = rp = 0;
	
	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
 
 	while(wp > rp) { ... }
}

 

이제 큐에 담긴 좌표를 하나씩 pop하면서 주변의 좌표의 거리를 재자.

while (wp > rp)
{
	QUEUE out = queue[rp++]; /* pop */
    
	for (int i = 0; i < 4; i++)
	{
		int nr = out.r + dr[i]; /* 주변 좌표 */
		int nc = out.c + dc[i];

		if (MAP[nr][nc] != 0 && visit[nr][nc] == 0) /* 벽이 아니고, 방문 하지 않은 곳 */
		{
			queue[wp].r = nr;
			queue[wp++].c = nc; /* push */

			visit[nr][nc] = 1; /* 방문 check */

			MAP[nr][nc] = MAP[out.r][out.c] + 1; /* 현재의 MAP보다 1 상승 */
		}
	}
}

out에 현재의 좌표보다 1칸이 더 필요하게 되므로, 주변의 좌표가 1씩 커지게 된다.

 

이제 (1, 2)를 pop해보자.

이미 방문한 (1, 1)은 큐에 담을 수 없고, 방문하지 않은 (1, 3)의 MAP이 (2 + 1 = 3)으로 변경된다.

 

다음으로 (2, 1)을 pop해보자.

마찬가지로 (1, 1)은 다시 담지 않으므로, (3, 1)의 MAP이 3이 된다.

 

다시 (1, 3)을 pop하면 (1, 2)는 방문했기 때문에, (1, 4), (2, 3)이 큐에 들어간다.

남은 칸은 직접 손으로 그려가면서 마지막으로 9가 되는지 확인해보자.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 10)

int N, M;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX*MAX];
int rp, wp;

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)		
			scanf("%1d", &MAP[r][c]);

}

void output()
{
	for (int r = 0; r <= N + 1; r++)
	{
		for (int c = 0; c <= M + 1; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS(int r, int c)
{
	wp = rp = 0;
	
	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
	
	while (wp > rp)
	{
		QUEUE out = queue[rp++];
        
		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (MAP[nr][nc] != 0 && visit[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;

				MAP[nr][nc] = MAP[out.r][out.c] + 1;
			}
		}
	}
}

int main(void)
{
	input();

	BFS(1, 1);

	printf("%d\n", MAP[N][M]);

	return 0;
}

 

---

output 함수를 이용하여, BFS 과정을 체크해보자.

위의 예시대로 BFS가 종료되면 9가 정답이 되는 것을 확인할 수 있다.