[백준 2178] 미로 탐색 (C++)

이 문제는 전형적인 BFS 문제이다. DFS로도 풀 수 있겠지만, 특정 위치에서 다른 위치로의 거리는 BFS로 접근하는 것이 더 편하기 때문에, BFS 풀이만 다루도록 할 것이다.

먼저, 필자는 board배열의 (0, 0)부터 (n - 1, m - 1)에 미로를 저장할 것이기 때문에, BFS의 시작점은 (0, 0)이고 거리는 1이 된다.

그리고, 다음 위치를 계산하여, 해당 범위를 벗어나지 않으며, 방문하지 않은 이동 가능한 칸을 큐에 삽입하고 거리를 1 증가시켜 저장한다.

이를 코드로 나타내면 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
string board[101];
int dist[101][101];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> board[i];
  
    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 1;
  
    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (board[nx][ny] == '0' || dist[nx][ny]) continue;
            q.push({nx, ny});
            dist[nx][ny] = dist[x][y] + 1;
        }
    }
  
    cout << dist[n - 1][m - 1];
}