[Baekjoon] 2178 - 미로 탐색 (C++)

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

2178번: 미로 탐색

BFS(breadth-first search)를 이용해 가장 짧은 거리를 구할 수 있는지 묻는 문제입니다. 한 번 나아갈 때마다 한 칸씩 나아갈 수 있으므로 가중치가 모두 1인 그래프에서 탐색하는 문제로 볼 수 있습니다. 가중치가 1이기 때문에 간단히 BFS를 이용해서 최단 거리를 구할 수 있죠. BFS 알고리즘을 구현할 수 있으면 크게 어려운 문제는 아닙니다.

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class Point
{
public:
	int x;
	int y;

	Point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
};

int n, m;
int maze[100][100];
int shortDistance[100][100];

void calcDistance()
{
	queue<Point> pList;

	// 시작 좌표 입력 및 기록
	pList.push(Point(0, 0));
	maze[0][0] = 0;
	shortDistance[0][0] = 1;

	while (!pList.empty()) {
		int x = pList.front().x;
		int y = pList.front().y;
		pList.pop();

		// 이미 도착했으면 종료
		if (x == m - 1 && y == n - 1) {
			break;
		}

		// 왼쪽
		if (x > 0 && maze[y][x - 1]) { 
			pList.push(Point(x - 1, y));
			maze[y][x - 1] = 0;
			shortDistance[y][x - 1] = shortDistance[y][x] + 1;
		}

		// 오른쪽
		if (x < m - 1 && maze[y][x + 1]) { 
			pList.push(Point(x + 1, y));
			maze[y][x + 1] = 0;
			shortDistance[y][x + 1] = shortDistance[y][x] + 1;
		}

		// 위
		if (y > 0 && maze[y - 1][x]) { 
			pList.push(Point(x, y - 1));
			maze[y - 1][x] = 0;
			shortDistance[y - 1][x] = shortDistance[y][x] + 1;
		}

		// 아래
		if (y < n - 1 && maze[y + 1][x]) {
			pList.push(Point(x, y + 1));
			maze[y + 1][x] = 0;
			shortDistance[y + 1][x] = shortDistance[y][x] + 1;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;

	// 미로 입력
	for (int y = 0; y < n; y++) {
		string s;
		cin >> s;

		for (int x = 0; x < m; x++) {
			maze[y][x] = s[x] == '1' ? 1 : 0;
		}
	}

	// BFS 탐색으로 가장 짧은 거리를 구한 뒤 출력
	calcDistance();
	cout << shortDistance[n - 1][m - 1] << "\n";

	return 0;
}