[C++] BFS 관련 문제 (백준 2178번, 미로 탐색)

[C++] 넓이 우선 탐색 (BFS)

BFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2178번 "미로 탐색" 문제를 풀이해본다.

---

미로 탐색 문제에서 BFS는 시작점에서 가까운 정점부터 탐색하므로, 목표 지점에 도달했을 때 찾은 경로는 항상 최단 경로가 된다.

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

문제 분석 및 해결 전략

이 문제는 최단 거리 (최소 이동 횟수)를 구하는 문제이므로 BFS가 적합하다. BFS는 탐색하는 순간 최단 거리임을 보장하기 때문에, 도착점에 처음 도달한 순간이 답이 된다. 이게 가능한 이유는 큐의 특성에서 찾을 수 있다. 이해를 돕기 위해 4 × 6 그래프에서 BFS를 쓸 때 큐에 어떤 방식으로 저장될 수 있을지를 그림으로 그려보면 다음과 같다.

(1,1)에서 시작하더라도 (3,3)을 반드시 지나므로 (3,3)부터 큐에 들어가는 좌표를 순서대로 써보았다.

그림에서 녹색과 파란색 모든 경로에 대해 찾으면서 큐에 먼저 들어온 것부터 pop()하다보면 목적지가 나오게 되고, 이 때 종료하고 거리를 계산하면 된다. 거리를 구하기 위해 매 턴마다 큐에 있는 모든 좌표를 빼주어야 한다. 이는 아래 코드를 보면 더 수월하게 이해할 수 있을 것이다.

구현

위에서 이야기한 BFS를 코드로 구현했다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> maze;      // 미로 정보
vector<vector<bool>> visited;  // 방문 여부

int dx[4] = {1, -1, 0, 0};  // 하, 상, 우, 좌 (문제에서 찾고자 하는 좌표는 가장 오른쪽 아래에 있음)
int dy[4] = {0, 0, 1, -1};  

int bfs(int startX, int startY, int endX, int endY, int n, int m) {
    queue<int> qx, qy;  // x, y 좌표를 따로 저장하는 큐
    qx.push(startX);
    qy.push(startY);
    visited[startX][startY] = true;

    int distance = 1;  // 시작 위치도 거리 1로 포함

    while (!qx.empty()) {
        int size = qx.size();
        for (int i = 0; i < size; i++) {
            int x = qx.front();
            int y = qy.front();
            qx.pop();
            qy.pop();

            // 목적지에 도착하면 즉시 반환
            if (x == endX && y == endY) {
                return distance;
            }

            // 4방향 이동 (상하좌우 모두 확인)
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (maze[nx][ny] == 1 && !visited[nx][ny]) {
                        qx.push(nx);
                        qy.push(ny);
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        distance++;  // 한 턴이 끝날 때마다 거리 증가
    }
    return -1;  // 도달 불가능한 경우
}

int main() {
    int n, m;
    cin >> n >> m;
    
    maze.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));

    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < m; j++) {
            maze[i][j] = row[j] - '0';
        }
    }

    int result = bfs(0, 0, n - 1, m - 1, n, m);
    cout << result << endl;

    return 0;
}

큐에 좌표를 깔끔하게 넣는 방법으로 pair가 있지만 이번 글에서는 그런 것들을 모른다고 가정하고 코드를 작성했다.

매 턴마다 큐에 들어있는 좌표를 모두 꺼내기 위해 큐의 사이즈만큼 반복되는 for문을 사용했고, 모든 인접 좌표에 대해 확인할 수 있는 for문을 사용했다. 그리고 그 턴이 끝날 때에 거리에 1씩 더하는 식으로 거리를 확인할 수 있다.

---

BFS는 한 번 방문한 좌표를 다시 방문하지 않기 때문에, 먼저 도착점에 도달하는 경로가 최단 거리다.
그리고 모든 경로를 탐색하면서 한 번씩만 방문한다. 큐를 사용해 같은 거리 그룹을 한꺼번에 처리하므로, 거리 정보가 정확하게 유지된다.

 

이런 부분에 있어서 그래프나 미로탐색 문제에서 자주 사용되는 알고리즘이며, 잘 학습하고 더 다양한 문제에 적용해보아야겠다.