[백준 - 2206] 벽 부수고 이동하기 - C++

분류: bfs, bfs 응용, 3차원 bfs /

 

문제

문제 링크

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

풀이

- 일반 BFS -> 벽까지 거리 저장 -> 벽에서부터 BFS

#include <iostream>
#include <queue>
using namespace std;

struct xy { int x, y; };
char board[1000][1001];
int dist[1000][1000];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M; cin >> N >> M;
    if(N * M == 1) { cout << 1; return 0; }
    for(int i=0; i<N; i++) cin >> board[i];

    queue<xy> Q, W;
    dist[0][0] = 1; 
    Q.push({0, 0});
    while(!Q.empty()) {
        int x = Q.front().x, y = Q.front().y; Q.pop();
        for(int d=4; d--;) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx<0 || nx >=N || ny<0 || ny>= M) continue;
            if(dist[nx][ny]) continue;
            dist[nx][ny] = dist[x][y] + 1;
            if(board[nx][ny] == '0')
                Q.push({nx, ny});
            else
                W.push({nx, ny});
        }
    }
    int ans = dist[N-1][M-1];
    
    while(!W.empty()) {
        int x = W.front().x, y = W.front().y; W.pop();
        int nxt = dist[x][y] + 1;
        for(int d=4; d--;) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx<0 || nx >=N || ny<0 || ny>= M) continue;
            if(board[nx][ny] == '1') continue;
            if(dist[nx][ny] == 0 || nxt < dist[nx][ny]) {
                dist[nx][ny] = nxt;
                W.push({nx, ny});
            }
        }
    }
    if(ans == 0 || ans > dist[N-1][M-1])
        ans = dist[N-1][M-1];
        
    cout << (ans ? ans : -1);
}

먼저 완탐을 생각해보자. 벽 통과 없이 한번, 벽을 하나씩 없애보며 bfs를 돌린 뒤 최솟값을 찾으면 당연히 시간초과가 날 것이다. 바로 패스.

 

그 다음 떠오른 생각은 3차원 bfs.

[프로그래머스 - 67259] [카카오 인턴] 경주로 건설 문제가 생각났다.

문제는 2차원이지만 조건에 따라 최단 거리가 달라져 최초 값이 최단 거리가 아닐 수 있는 경우다.

이 경우 2차원 맵에 조건 차원을 추가해 조건마다 최단거리를 기록한다.

`경주로 건설 문제`에서는 조건이 방향 4개였다. 따라서 방향 차원을 하나 추가하고 4개의 레이어를 두어 풀었다.

이 문제에서는 벽을 부순적이 있는 지에 대한 차원을 추가하고 2개의 레이어를 두어 벽을 뚫고 왔을 때 최단거리와 길만 따라 왔을 때의 최단거리를 각각 계산하면된다.

 

이를 구현하려고 생각해보니 결국 벽에 도달해도 바로 무시하는 것이 아니라 벽에 거리를 저장하고 나중에 BFS를 돌리면 되지 않나 하는 생각이 들었다.

가장 처음 패스했던 완전 탐색 풀이의 문제점은 모든 벽을 하나씩 없애며 각각에 대해 bfs를 처음부터 수행해 비효율이 발생하는 것이었다.

처음 bfs를 돌며 벽을 마주했을 때 벽까지의 거리를 기록하고 벽에서부터 bfs를 수행하면 되지 않을까?

위 풀이는 두가지 파트로 구성된다.

1. 벽을 하나도 통과하지 않는 경로 BFS
   • 벽을 통과하지 않고 BFS를 돌며 만나는 벽을 별도로(`W`)저장하고 벽까지의 거리를 기록한다.
2. 벽을 통과한 경로 BFS
   • 출발지에서 갈 수 있는 모든 벽(`W`)에서 BFS를 수행한다.
   • 이때 먼저 지나간 경로(`dist`)의 최단 거리보다 짧은 경우에만 경로 탐색을 계속한다.

벽에서 부터 BFS를 도는 모든 경로에서 이미 벽을 통과한 상태이다. 따라서 벽에서 부터 출발 이후 경로는 벽을 하나도 통과하지 않는 BFS의 경로와 완전히 겹친다. 따라서 기록된 거리보다 길거나 같을 경우 고려할 필요가 없다.

 

- 3차원 BFS

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

char board[1000][1001];
int dist[1000][1000][2];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M; cin >> N >> M;
    for(int i=0; i<N; i++) cin >> board[i];

    int ans = -1, endX = N-1, endY = M-1;
    queue<tuple<int, int, bool>> Q;
    dist[0][0][0] = dist[0][0][1] = 1;
    Q.push({0, 0, 0});
    while(!Q.empty()) {
        int x, y; bool broken;
        tie(x, y, broken) = Q.front(); 
        if(x == endX && y == endY) {
            ans = dist[x][y][broken];
            break;
        }
        Q.pop();
        int nxt = dist[x][y][broken] + 1;
        for(int d=4; d--;) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx<0 || nx >=N || ny<0 || ny>=M) continue;
            if(board[nx][ny] == '0') {
                if(dist[nx][ny][broken]) continue;
                dist[nx][ny][broken] = nxt;
                Q.push({nx, ny, broken});
            }
            else if(!(broken || dist[nx][ny][1])) {
                dist[nx][ny][1] = nxt;
                Q.push({nx, ny, 1});
            }
        }
    }
    cout << ans;
}

두번째로 들었던 생각으로 다시 풀어봤다. 시간이 대충 첫번째 풀이의 절반 정도가 걸렸다.

3차원으로 풀 경우 모든 경우에서 퍼져나가다가 하나라도 도착하는 순간 최단 거리임으로 탐색을 종료한다.

하지만 첫번째 풀이의 경우 벽을 뚫고 바로 도착한 경우에도 벽을 뚫지 않는 첫번째 BFS의 결과를 계산해야한다.

3차원으로 한번에 돌리는게 2배 정도 빠른게 당연하다.

• 길이고(`board == 0`), 처음 가는 길이라면(`dist[nx][ny][broken] == 1`) 이동
• 벽이라면(`board == 1`) 벽을 깬적이 없고(`!broken`) 처음 깨는 벽이라면(`dist[nx][ny][1] == 0`) 벽 깨고 이동