BFS 문제 풀기 -> 미로 찾기

이와 비슷한 문제를 풀어본 적은 있지만 BFS문제라는 생각을 하고서 풀어본건 이번이 처음이다.

 

해당 문제는 4방향으로 이동 가능한 미로의 길을 따라 움직이며 (M,N)위치에 도달하기까지의 최종 움직인 횟수를 출력하는 문제였다. 그러므로 이동 가능한 모든 좌표에 최단거리를 계산하여 저장하고, (M,N)까지의 최단거리를 출력하게 된다.

자료구조는 큐를 사용하며 큐에 담긴 좌표들을 모두 검색하며 이동 가능한 방향이 이미 방문한 노드가 아니라면 해당 방향에 대한 좌표를 큐에 다시 담고, 해당 방향의 좌표에 대한 최단거리를 저장한다. 이를 재귀적으로 반복하면 최종적으로 모든 이동 가능한 좌표에 대한 최단거리를 저장할 수 있게 된다.

 

재귀 개념을 이용하여 접근하면서 직관적이게 해당 개념에 대해 알아보고 풀어나갈 수 있었다. 해당 개념에 대한 이해가 아직 부족하다는 생각이 들어 더 많은 문제를 접해봐야겠다는 생각이 들었다.

 

아래는 제출한 코드입니다. 포바~!

int main()
{
	// 목표 위치
	int M;
	int N;

	cin >> N >> M;

	string map[102];
	int visit[102][102];

	for (int i = 0; i < N; i++)
			cin >> map[i];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			visit[i][j] = 0;

	// 현재 위치
	int xPos = 0;
	int yPos = 0;

	// Up Down Left Right
	int dx[4] = {0,0,-1,1};
	int dy[4] = {1,-1,0,0};

	queue<vector<int>> Queue;
	Queue.push({ xPos,yPos });

	while (!Queue.empty())
	{
		// queue에서 탐색할 좌표를 하나 꺼낸다.
		vector<int> Pos = Queue.front();
		Queue.pop();

		// 4방향에 대해서 검색
		for (int i = 0; i < 4; i++)
		{
			int tempX = Pos[0] + dx[i];
			int tempY = Pos[1] + dy[i];

			if (tempX < 0 || tempX >= N || tempY >= M || tempY < 0) continue;

			// 벽이 아니고, 방문한 적이 없다면 해당 좌표를 큐에 담는다.
			if (map[tempX][tempY] != '0' && visit[tempX][tempY] == 0)
			{
				visit[tempX][tempY] = visit[Pos[0]][Pos[1]] + 1;

				if (tempX == N-1 && tempY == M-1) { 
					cout << visit[tempX][tempY] + 1; 
					return 0;
				}

				Queue.push({ tempX,tempY });
			}
		}
	}

	return 0;
}