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

 

 

 

문제

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 방법으로 문제를 풀어서 제출했다.

​

역시나.. 시간 초과.

문제를 고민하며 어쩌면 골드 그 이상의 난이도일 수, 아니 차라리 그랬으면 좋겠다는 상상을 했다.

​

 

 

본론으로 들어가자. 이 문제의 핵심은 방문 처리 배열에 있다.

먼저 현재 위치가 (x, y)이고 다음 위치를 (X, Y)라고 한다면, 나올 수 있는 경우의 수는 4가지 이다.

​

(1) 아직 벽을 부순 적이 없고, (X, Y)가 0인 경우

(2) 아직 벽을 부순 적이 없고, (X, Y)가 1인 경우 → (X, Y)의 벽을 부술 경우로 해석. 이유는 하단 설명 참고.

(3) 이미 벽을 하나 부쉈고, (X, Y)가 0인 경우

(4) 이미 벽을 하나 부쉈고, (X, Y)가 1인 경우

 

여기서 (4)의 경우는 이미 벽을 하나 부쉈으므로 (X, Y)로 이동할 수 없기 때문에 고려하지 않아도 된다. 그러면 3가지 경우로 줄어든다.

​

​

벽을 이미 부쉈는지의 여부는 주어지는 2차원 맵에 벽의 파손 여부를 참조하는 차원을 하나 더하여 3차원의 방문 처리 배열로 구현하면 된다. 코드에서 v[2][1001][1001]로 선언되어 있다. 0은 아직 벽을 부수지 않음을, 1은 벽을 이미 부쉈음을 의미.

​

 

 

(1)의 경우는 아직 벽을 부순 적이 없으면서 다음 위치인 (X, Y)가 0이기에 벽을 부술 필요가 없다. 따라서 다음 위치의 방문 배열도 v[0][X][Y] = 1로 처리된다.

 

(2)의 경우는 아직 벽을 부순 적이 없으면서 다음 위치인 (X, Y)가 1이다. 이 경우에서는 벽을 부수는 처리를 하므로 다음 위치의 방문은 v[1][X][Y] = 1로 처리된다. (참고로 다른 위치의 벽들은 (1)만을 순회하던 유닛이 벽을 만나게 되면 (2)의 경우가 되므로 언젠가 부서질 것이다.)

 

(3)의 경우는 이미 벽을 하나 부쉈지만 다음 위치인 (X, Y)가 0이기 때문에 해당 위치로 이동하면 된다. 이때의 방문은 v[1][X][Y] = 1이다.

​

그렇다면 코드를 살펴보자. 2차원 배열의 위치 x, y와 이동 횟수를 세는 count, 벽을 부쉈는지 기억하는 wall 총 4개의 변수를 queue<pair<pair<int, int>, pair<int, int>>> 형에 저장할 수도 있지만 가독성을 위해 두 개의 큐에 분리해서 저장하겠다. 해당 변수들은 서로 종속되지만 큐는 순서를 지켜주므로 실행에 아무런 지장은 없다.

 

 

 

코드

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

int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int n, m;
bool d[1001][1001], v[2][1001][1001];

int bfs() {
    v[1][1][1] = 1;
    v[0][1][1] = 1;
    queue<pair<int, int>> xy;
    queue<pair<int, int>> count_wall;

    xy.push({ 1,1 });
    count_wall.push({ 1,0 });

    while (!xy.empty()) {
        int x = xy.front().first;
        int y = xy.front().second;
        int count = count_wall.front().first;
        int wall = count_wall.front().second;
        xy.pop(); count_wall.pop();

        if (x == n && y == m) return count;

        for (int i = 0; i < 4; i++) {
            int X = x + dx[i], Y = y + dy[i];

            if (X && Y && X <= n && Y <= m) { // 범위 체크는 공통
            
                // (1) 벽 부순 적 없으면서 다음 위치가 0일 때
                if (!d[X][Y] && !wall && !v[wall][X][Y]) {
                    v[wall][X][Y] = 1;
                    xy.push({ X,Y });
                    count_wall.push({ count + 1, wall });
                }
                
                // (2) 벽 부순 적 없지만 다음 위치가 벽이면서 부술 때
                else if (d[X][Y] && !wall && !v[wall + 1][X][Y]) {
                    v[wall + 1][X][Y] = 1;  // (X, Y)의 벽을 부수므로 v[1][X][Y]를 1로 처리
                    xy.push({ X,Y });
                    // 큐에 벽을 부쉈을 때의 값으로 푸쉬
                    count_wall.push({ count + 1, 1 });
                }
                
                // (3) 벽 부순 적 있으면서 다음 위치가 0일 때
                if (!d[X][Y] && wall && !v[wall][X][Y]) {
                    v[wall][X][Y] = 1;
                    xy.push({ X,Y });
                    count_wall.push({ count + 1, wall });
                }

                // (4) 벽을 부순 적 있으면서, 다음 위치가 벽일 때는 처리하지 않아도 됨
            }
        }
    }
    return -1;  // (n, m)에 도달할 수 없을 때 -1 반환
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", d[i] + j);

    cout << bfs();
}