[C++] BFS 관련 문제 (백준 2206번, 벽 부수고 이동하기)

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

BFS 활용 문제 중 하나로 백준 온라인 저지의 2206번 "벽 부수고 이동하기" 문제를 풀이해본다.

---

이전 글인 "미로 탐색" 문제에서 벽이 하나 생긴 형태의 문제로 볼 수 있다.

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

문제 분석 및 해결 전략

최단 경로 문제이므로 BFS를 사용해야 한다는 것은 쉽게 생각할 수 있다. 여기에 벽을 부순 이력까지 같이 관리를 해주어야 한다. 그리고 각 좌표에 도달했을 때 거리 계산 내용도 벽 부순 이력에 따라 나눠서 관리를 해주어야 한다.

왼쪽과 같은 맵에서, 눈여겨볼 두 가지 경우를 오른쪽에 그려보았다.

첫 번째로, 벽을 한 번 부쉈으면 벽 부순 여부가 T로 바뀐다. 그리고 (2,1)에서 갈 수 있는 곳을 보면 두 곳 다 벽이 있어 진행할 수 없다. 그러면 큐에 추가할 수 있는 좌표가 없다.

다음으로는 두 가지 길이 나오는 경우이다. 경로를 단순하게 어떤 변수에 저장해서 더하는 식으로 하면 문제가 발생할 수 있다. 그래서 거리에 대해서도 방문 여부에 따라서 둘로 나누는 방법이 필요할 것이다.

 

예시 맵에 대해 상황을 그려보면서, BFS를 문제에 맞게 구현하기 위한 조건들을 생각해볼 수 있었다.

구현

BFS를 이용하면서 벽을 부순 여부까지 관리할 수 있는 코드를 구현했다.

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int maze[1000][1000];   // 원본 맵 정보
int dist[1000][1000][2]; // 방문 여부 및 거리 저장 (벽 부쉈을 때 / 안 부쉈을 때 구분)
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int bfs() {
    queue<pair<int, pair<int, int>>> q; // {벽 부순 여부, {x, y}}
    q.push({0, {0, 0}});
    dist[0][0][0] = 1; // 시작 위치 거리 설정 (백준의 예제 입출력 1을 통해 시작점에서부터 1을 가져야 한다는 것을 확인)

    while (!q.empty()) {
        int broken = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();

        // 도착 지점에 도달하면 거리 반환
        if (x == N - 1 && y == M - 1)
            return dist[x][y][broken];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위를 벗어나면 무시
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;

            // 벽을 만났을 경우
            if (maze[nx][ny] == 1 && broken == 0) {
                dist[nx][ny][1] = dist[x][y][0] + 1;
                q.push({1, {nx, ny}});
            }
            // 이동 가능한 경우 (벽이 아니고 방문하지 않았다면)
            else if (maze[nx][ny] == 0 && dist[nx][ny][broken] == 0) {
                dist[nx][ny][broken] = dist[x][y][broken] + 1;
                q.push({broken, {nx, ny}});
            }
        }
    }
    
    return -1; // 도착 불가능한 경우
}

int main() {
    cin >> N >> M;
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;
            maze[i][j] = c - '0';
        }

    cout << bfs() << endl;
    return 0;
}

상하좌우 네 방향에 대해서 확인을 할 때에, 미로를 벗어나는 범위는 무시하는 경우, 이동 가능한 두 가지 경우에 대해 좌표와 거리 데이터를 큐에 넣는 식으로 코드를 구현했다. 입력을 받는 경우에는, 숫자들이 붙어있기 때문에 입력을 char 형식으로 받았다. 그리고 미로 배열은 int로 정의를 했기 때문에 '0'을 빼주면 0과 1로 변환했다.

코드로 써놓고 보면 간단한 것 같긴 한데, 이걸 이해하고 케이스들을 정리하는 것이 쉽지는 않았다.

---

이전에 풀었던 2178번 "미로 탐색" 문제보다는 조금 까다로운 것 같다.

벽 부수기 문제도 문제 종류가 더 있는 것 같아서, 더 풀이해볼 수 있을 것이다.