백준 2206 벽 부수고 이동하기

최단 경로를 구하는 문제이고, 한 칸 이동하는 것을 가중치 1로 둘 수 있으므로 bfs로 풀 수 있는 문제다.

벽을 1번 부순 경우와 벽을 부수지 않은 상태로 이동하는 경우가 다르기 때문에 다른 정점으로 봐야 한다.

따라서 3차원 배열로 선언하여 벽을 부쉈을 때 비용과 부수지 않았을 때 비용을 구분하여 준다.

 

그리고 queue에는 벽을 부쉈는지 여부도 전달해주어야 한다.

처음에는 [row][col][0]에 비용을 저장하고, [row][col][1]에 벽을 부순 여부를 저장했는데, 이는 어느 특정한 칸을 왔을 때 벽을 한 번 부쉈는지 안 부쉈는지 경우의 수를 나누지 않은 것이었다.

아래는 처음 생각했던 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int maze[1000][1000];
int dist[1000][1000][2];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
 
    //0은 거리를 저장, 1은 몇개를 깼는지 저장
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dist[i][j][0] = -1;
            dist[i][j][1] = 0;
        }
    }
 
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    dist[0][0][0] = 1;
 
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        /*
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf("%d ", dist[i][j][0]);
            }
            printf("\n");
        }
        printf("\n");
        */
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
 
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //이동할 수 있고, 아직 방문하지 않은 곳.
                if (dist[nr][nc][0] == -1 && maze[nr][nc] == 0) {
                    dist[nr][nc][1] = dist[row][col][1];
                    dist[nr][nc][0] = dist[row][col][0] + 1;
                    q.push(make_pair(nr, nc));
                }
                //벽이지만 아직 방문하지 않은 곳. 아직 벽을 한 번도 안 깬경우
                if (dist[nr][nc][0] == -1 && maze[nr][nc] == 1 && dist[row][col][1] == 0) {
                    dist[nr][nc][0] = dist[row][col][0] + 1;
                    q.push(make_pair(nr, nc));
                    dist[nr][nc][1]++;
                }
            }
        }
    }
    /*
    if (dist[n - 1][m - 1][0] != -1 && dist[n - 1][m - 1][1] != -1) 
        printf("%d\n", min(dist[n - 1][m - 1][1], dist[n - 1][m - 1][0]));
    else if(dist[n - 1][m - 1][0] != -1) 
        printf("%d\n", dist[n - 1][m - 1][0]);
    else if(dist[n - 1][m - 1][1] != -1)
        printf("%d\n", dist[n - 1][m - 1][1]);
    else 
        printf("-1\n");
    */
    if(dist[n-1][m-1][0] == -1)printf("-1\n");
    else printf("%d\n", dist[n - 1][m - 1][0]);
    return 0;
}

하지만 이 코드는 아래와 같은 예제를 해결하지 못한다.

5 8
01000000
01010000
01010000
01010011
00010010

분명히 (n,m)에 갈 수 있는데도 결과는 -1이 나온다.

문제는 이미 한 번 벽을 깬 후 진행되는 결과가 먼저 방문해버렸기 때문에 그 진행 경로에 있는 정점은 모두 벽을 1번 깬 것으로 나와버리기 때문에, 마지막에 갇힌 도착점을 벽을 뚫지 못해서 였다.

 

따라서 한 정점을 방문할 때 이미 벽을 뚫고 온 경우와 뚫지 않고 온 경우를 나눠서 생각해줘야 한다.

tuple과 tie를 쓰는 법도 익히게 되었다.

 

수정한 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
 
int maze[1000][1000];
int dist[1000][1000][2];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
 
    //부순 경우와 부수지 않은 경우 모두 -1로 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dist[i][j][0] = -1;
            dist[i][j][1] = -1;
        }
    }
 
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(0, 0, 0));
    dist[0][0][0] = 1;
 
    while (!q.empty()) {
        int row, col, block;
        tie(row,col,block) = q.front();
        q.pop();
        /*
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf("%2d ", dist[i][j][1]);
            }
            printf("\n");
        }
        printf("\n");
        */
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
 
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //이동할 수 있고, 아직 방문하지 않은 곳.
                if (dist[nr][nc][block] == -1 && maze[nr][nc] == 0) {
                    dist[nr][nc][block] = dist[row][col][block] + 1;
                    q.push(make_tuple(nr, nc, block));
                }
                //벽이지만 아직 방문하지 않은 곳. 아직 벽을 한 번도 안 깬경우
                if (dist[nr][nc][block] == -1 && maze[nr][nc] == 1 && block == 0) {
                    dist[nr][nc][block + 1] = dist[row][col][block] + 1;
                    q.push(make_tuple(nr, nc, block + 1));
                }
            }
        }
    }
    //한 쪽 경우의 수가 도착하지 못하면 다른 경우의 수가 답이 되고, 둘 다 도착점에 도달가능하면 최소 비용을 고른다.
    if (dist[n - 1][m - 1][0] != -1 && dist[n - 1][m - 1][1] != -1) 
        printf("%d\n", min(dist[n - 1][m - 1][1], dist[n - 1][m - 1][0]));
    else if(dist[n - 1][m - 1][0] != -1) 
        printf("%d\n", dist[n - 1][m - 1][0]);
    else if(dist[n - 1][m - 1][1] != -1)
        printf("%d\n", dist[n - 1][m - 1][1]);
    else 
        printf("-1\n");
    
    
    return 0;
}