[BOJ] 2178 미로탐색 - 최단 경로, BFS

2178번: 미로 탐색

예제(더 많은 예제는 링크에 있습니다.)

4 6
101111
101010
101011
111011

ans : 15

---

BFS의 가장 대표적인 문제 중 하나로, 최단경로 탐색 문제이다. 최단 경로가 왜 BFS냐면, 여러 갈래 길이 나왔을 때 마치 BFS처럼 너비 우선으로 길을 찾으면서 진행하기 때문이다. 최단경로가 나오면 BFS를 가장 먼저 고려해 보자. 기본적인 BFS 구현에서 visited 배열만 dist 배열로 바꿔서 거리를  표시해 주면 된다.

 

dist의 모든 칸을 -1로 두고, BFS의 시작점이 (0, 0)으로 고정이기에 거기부터 탐색을 시작하면 된다.

/** BFS 2178 미로탐색 **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 102
using namespace std;

string board[MAX];
int dist[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m; // n행 m열

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

    queue<pair<int, int>> Q;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        fill(dist[i], dist[i] + m, -1);
    }

    for (int i = 0; i < n; i++)
    {
        cin >> board[i];
    }

    dist[0][0] = 1;
    Q.push(make_pair(0, 0));

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (dist[nx][ny] != -1 || board[nx][ny] != '1')
                continue;
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            Q.push(make_pair(nx, ny));
        }
    }
    cout << dist[n - 1][m - 1];
}