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

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

2206번: 벽 부수고 이동하기

문제

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

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

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

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

 

풀이

1. 시작점에서 도착점까지의 최단 거리를 구하는 문제이다. BFS 로 접근하면 된다.

2. 특이한 점은 벽을 1개까지 부술 수 있다는 것인데, 이에 따라서 한 위치를 방문할 수 있는 방법이 2가지 존재한다. 

첫번째는, 벽을 부수지 않고 특정 점에 도달하는 것, 두번째는 벽을 부수고 도달한 방법이다. 따라서 visited 배열을 3차원으로 선언해서, 그냥 도착한 것과 부수고 도착한 것을 저장할 수 있도록 한다.

3. 구조체 Pose 에는 num 변수를 사용해서 특정 점에 도착했을 때, 벽을 몇 번 부쉈는지 기록할 수 있도록 한다.

4. 따라서, 한 점에 대해 두 가지 경우를 큐에 push 할 수 있게 되고, 모든 경우의 수를 따질 수 있게 된다. 방문 체크 배열을 2차원으로 선언할 경우, 최단 거리 기준으로 체크가 되기 때문에 부수지 않고 돌아서 방문하는 경우를 알 수 없다. 

예시) 

0101

0010 일 때, right-down-left-up 순으로 방문할 경우, (2, 2) 지점은 벽을 한번 부수고 도착한 점으로 먼저 업데이트 되고 다시 방문하지 않게 된다. 따라서 이 경우 도착점에 도달할 수 없는 경우가 되는데, 이 경우를 방지해야 한다. 따라서, 체크 배열을 3차원으로 생성하고, 부수고 도착했을 때( visited[2][2][1] = 1) 를 따로 체크한다. 이렇게 되면, visited[2][2][0]=0인 상태이기 때문에 (2, 1)을 거쳐서 방문하는 경우를 vistied[2][2][0]에 체크할 수 있다. 따라서 (2, 3)을 부수고 방문할 수 있다.

 

5. push 하면서 dist 벡터를 업데이트 하면 최단 거리를 업데이트 할 수 있다.

리뷰

1. dist[nr][nc] = min( dist[nr][nc], dist[p.row][p.col] + 1) 로 했다가 오답 처리가 되었었다.

2. 다익스트라를 생각하면서 코딩을 했기 때문에 실수했던 부분이었다.

3. 위 처럼 거리를 업데이트 할 경우, 벽을 부수지 않고 돌아서 특정 점에 방문한 것이 업데이트 되지 않는다.

4. dist[nr][nc] = dist[p.row][p.col] + 1 이 될 경우, 벽을 부수고 가는 것이 빠른 경우가 먼저 업데이트 되겠지만, 최종 단계에서 벽을 만나는 경우(이미 벽을 부숴서 갈 수 없는 경우), 벽을 만나지 않고 오는 경우로 결국 업데이트 되게 된다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>

using namespace std;

int visited[1001][1001][2];

struct Pose{
    int row;
    int col;
    int num;
    Pose (int a, int b, int c){
        row=a;
        col=b;
        num=c;
    }
};

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

int main()
{
    // freopen("2206.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> map(1001, vector<int> (1001, 0));
    vector<vector<int>> dist(1001, vector<int> (1001, INT_MAX));    

    string str; 
    for (int i=0; i<n; i++) {
        cin >> str;
        for (int j=0; j<m; j++) {
            if (str[j]-'0' == 1) map[i+1][j+1] = 1;
        }
    }
    queue<Pose> q;
   
    if (map[1][1] == 1) q.push(Pose(1, 1, 1));
    else q.push(Pose(1, 1, 0));
    dist[1][1] = 1;
    while (!q.empty()) {
        Pose p = q.front();
        q.pop();

        if (visited[p.row][p.col][p.num]) continue;
        visited[p.row][p.col][p.num] = 1;
        if (p.row == n && p.col == m) break;

        for (int i=0; i<4; i++) {
            int nr = p.row + dr[i];
            int nc = p.col + dc[i];

            if (nr < 1 || nr > n || nc < 1 || nc > m) continue;

            // visited[nc][nr][p.num] 을 사용해서 벽을 부수지 않고 nc, nr에 방문한 것과,
            // 벽을 부수고 nc, nr에 도착한 것, 모두 push 할 수 있도록 함
            if (map[nr][nc] == 1) {
                if (p.num == 0) {
                    if (!visited[nr][nc][p.num]) {
                        q.push(Pose(nr, nc, p.num+1));
                        dist[nr][nc] = dist[p.row][p.col]+1;
                    }
                }
            }
            else {
                // nr, nc에 대해 p.num이 0, 1인 경우 모두 push가능 
                if (!visited[nr][nc][p.num]) {
                    q.push(Pose(nr, nc, p.num));
                    dist[nr][nc] = dist[p.row][p.col]+1;
                }
            }
            
        }
    }

    if (dist[n][m] == INT_MAX) cout << -1 << endl;
    else cout << dist[n][m] << endl;

    return 0;
}