(백준/C++) 2178_미로 탐색

2178번: 미로 탐색 (acmicpc.net) 문제는 시작 위치에서 도착 위치인 (N - 1, M - 1)까지 이동할 때 지나야 하는 최소의 칸 수를 찾는 문제입니다. 이때, 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타냅니다.

접근법

이 문제는 최단 경로를 찾는 문제이므로 너비 우선 탐색(BFS) 알고리즘을 사용해서 풀어볼 수 있습니다.

탐색 제한

먼저, NxM 사이즈의 미로를 입력 받고, 그 크기에 맞는 visited 배열을 똑같이 만듭니다.

이 visited 배열을 사용하여 이미 방문한 위치를 다시 방문하지 않도록 하겠습니다.

거리 계산 방법

이 문제에서 중요한 것은 미로를 탐색 하면서 최단 거리가 몇 인지 계산해야 하는 것입니다.

저는 Coord 구조체를 사용하여 x, y 좌표와 이동 거리(step)을 함께 관리하도록 설계했습니다.

struct Coord
{
	int x;
	int y;
	int step;
};

이렇게 하면, 다음 좌표로 이동할 때, 해당 좌표까지의 거리를 관리할 수 있습니다.

도착 설정

미로의 끝에 도달하면, 현재 Coord의 step 값이 바로 최단 거리가 됩니다.

---

풀이

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

struct Coord
{
	int x;
	int y;
	int step;
};

int solveRtnStep(const vector<vector<bool>>& maze, Coord& start)
{
	vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));
	queue<Coord> q;

	// 방향 설정
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };

	// 시작 위치 설정
	visited[start.x][start.y] = true;
	q.push(start);

	// 탐색
	while (!q.empty())
	{
		Coord cur = q.front();
		q.pop();

		// 만약 도착했다면
		if (cur.x == maze.size() - 1 && cur.y == maze[0].size() - 1)
		{
			return cur.step + 1;
		}

		// 다음 미로 탐색
		for(int i = 0; i < 4; i++)
		{
			int nextX = cur.x + dx[i];
			int nextY = cur.y + dy[i];

			if(nextX >= 0 && nextX < maze.size() && nextY >= 0 && nextY < maze[0].size())
			{
				if(maze[nextX][nextY] && !visited[nextX][nextY]) // 미로가 1이고 방문하지 않았다면
				{
					Coord next = { nextX, nextY, cur.step + 1 }; // 다음 좌표와 거리 설정

					visited[nextX][nextY] = true;
					q.push(next);
				}
			}
		}
	}

	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<vector<bool>> maze(N, vector<bool>(M)); // 미로 만들기
	for (int i = 0; i < N; i++)
	{
		string input;
		cin >> input;
		for (int j = 0; j < M; j++)
		{
			maze[i][j] = (input[j] == '1');
		}
	}

	Coord start = { 0, 0, 0 };

	cout << solveRtnStep(maze, start);
}