[BOJ]2178번: 미로 탐색 (c++)

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

2178번: 미로 탐색

 

 

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 100;
int map[MAX][MAX];
bool check[MAX][MAX];
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };
int N, M;

struct info {
	int x;
	int y;
	int depth;
};

int bfs()
{
	// 큐 선언 후 시작점과 깊이값 push
	queue<info> q;
	q.push({ 0, 0, 1 });

	// 큐가 빌 때까지 반복문
	while (!q.empty())
	{
		info tmp = q.front();
		q.pop();
		int x = tmp.x;
		int y = tmp.y;
		int depth = tmp.depth;

		// 큐가 map[N][M]에 도착하면 깊이값 반환 및 종료
		if (x == N - 1 && y == M - 1)
		{
			return depth;
		}

		// 4가지 방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int new_x = x + dir_x[i];
			int new_y = y + dir_y[i];

			// 다음 지점이 map 범위 내에 있고
			if (0 <= new_x && new_x < N && 0 <= new_y && new_y < M)
			{
				// 다음 지점을 아직 방문하지 않았고 이동할 수 있는 칸일 때 
				if (!check[new_x][new_y] && map[new_x][new_y] > 0)
				{
					// 큐에 중복해서 push하지 않도록 check
					check[new_x][new_y] = true;
					// 다음 지점 위치와 현재 깊이보다 1 큰 값 push
					q.push({ new_x , new_y, depth + 1 });
				}
			}
		}
	}
	return 0;
}

int main()
{
	// 입력
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			scanf("%1d", &map[i][j]);
		}
	}

	// 너비우선 탐색으로 미로 순회 후 최소값 출력
	printf("%d\n", bfs());

	return 0;
}

 

기계적으로 처음에 dfs로 풀고 예제가 잘돌아가길래 제출했다가... 역시 실패했다 ㅋㅋ

 

 

이 문제는 최소 거리를 구하는 문제이다.

미로로 주어진 표를 그래프 혹은 트리라고 생각하면 편하다.

 

그래프로 생각하면 노드 map[0][0]에서 노드 map[N][M]까지 이르는 간선의 개수가 바로 최소 거리이다.

트리로 생각하면 최상위 노드 map[0][0]에서 노드 map[N][M]까지의 깊이가 최소 거리이다.

 

이렇게 bfs로 풀면 map[N][M]에 도달하는 것 자체로 지나온 칸의 (최소)개수를 알수 있다.

따라서 map[N][M] 지점에서 바로 return 할 수 있어 간편하다.

int bfs()
{
    ...

    // 큐가 map[N][M]에 도착하면 깊이값 반환 및 종료
    if (x == N - 1 && y == M - 1)
    {
        return depth;
    }

    ...
}

 

하지만 dfs로 풀면 map[N][M]에 도착했어도 이것이 최소의 경로로 왔는지 알수가 없다.

때문에 쓸데 없이 여러번 다양하게 map[N][M]을 방문해야 하고, 

dfs가 스택구조이므로 다시 처음위치로 돌아가기 까지...

 

dfs와 bfs의 차이점을 다시 잘 알아두자