[백준] 16933 벽 부수고 이동하기 3 (C++)

링크: https://www.acmicpc.net/problem/16933

문제

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

이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

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

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

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

---

풀이

BFS로 이동할 수 있는 곳들을 큐에 추가하며 (N, M)까지 이동하면 되는 문제이다.

그런데 문제 조건에서는 이동할 수 없는 벽이 존재하며 벽을 부수고 지나갈 수 있다.

또한 벽은 최대 K개까지만 부수고 이동할 수 있다.

 

따라서 방문 처리를 할 때 벽을 몇 개 부수고 좌표 (a, b)에 도달하였는지를 저장해야 한다.

벽을 0개 부수고 (a, b)에 도달하였다고 하더라도 가장 짧은 경로임이 보장되지 않고,

벽을 5개 부수고 (a, b)에 최단경로로 도달하였다고 하더라도 (N, M)까지 도달할 수 있는지를 모르기 때문에,

벽을 몇 개 부쉈는지를 방문 처리를 진행하며 모든 경우를 조사해야 한다.

 

그리고 밤에는 벽을 부술 수 없다는 조건이 존재하는데, 이를 해결하기 위해 날짜를 2일 더해 큐에 추가할 수 있다.

하지만, 이럴 경우 priority_queue를 사용하지 않는 이상 날짜가 꼬이게 되고 올바르지 않은 풀이이다.

따라서 날짜를 1일 더하고 큐에 같은 좌표를 추가하는 것이 옳다.

 

코드

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

char graph[1001][1001];
bool visited[1001][1001][11];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int bfs(int n, int m, int k){
    queue<vector<int>> que;
    // 일수, 벽, y, x 순으로 저장
    que.push({1, 0, 1, 1});

    while (!que.empty()){
        int date = que.front()[0];
        int walls = que.front()[1];
        int curY = que.front()[2];
        int curX = que.front()[3];

        if (curY == n && curX == m){
            return date;
        }
        que.pop();

        for (int i = 0; i < 4; i++){
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
            if (nextY < 1 || nextY > n || nextX < 1 || nextX > m){
                continue;
            }
            // 이동할 수 있는 경우
            if (graph[nextY][nextX] == '0' && !visited[nextY][nextX][walls]){
                que.push({date+1, walls, nextY, nextX});
                visited[nextY][nextX][walls] = true;
            }
            // 벽인 경우(부숴야 하는 경우)
            else{
                if (walls < k && !visited[nextY][nextX][walls+1]){
                    // 낮이면 그냥 추가
                    if (date % 2){
                        que.push({date+1, walls+1, nextY, nextX});
                        visited[nextY][nextX][walls+1] = true;
                    }
                    // 밤이면 하루 더 기다림
                    else{
                        que.push({date+1, walls, curY, curX});
                    }
                }
            }
        }
    }
    return -1;
}

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

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> graph[i][j];
        }
    }

    cout << bfs(n, m, k);
}