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

🔗알고리즘 문제

기본적인 BFS가 아닌 BFS 심화격인 문제이다. 단순히 check만 표시해야 하는 것이 아닌 3차원 구조를 사용해야 하는 것이 신박했다.

문제 분석

이 문제는 0, 0좌표에서 m, n 좌표까지 이동하는 최단 거리를 찾는 기본적인 길 찾기 문제이다.

단 이동하는 도중 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동할 수 있다.

발상 & 알고리즘 설계

이 문제는 지금까지 풀었던 길 찾기 문제처럼 칸마다 방문체크를 하나씩만 해주는 방식으로는 해결할 수 없습니다.

어떤 칸에 도달 했을 때 아직 벽을 부술 수 있는 상태일수도 벽을 이미 부수고 온 상태일 수도 있습니다. 벽을 안부수고도 현재 칸에 도달할 수 있지만 벽을 부수고 오는 것이 더 빠르다고 가정했을 때 현재 칸에서 최종 칸까지 이동하는 길이 벽에 막혀있다면 현재 상태로써는 최종 칸에 도달할 수 없다는 오답이 나옵니다.

이를 위해 방문체크를 두 가지 세계에서 해주어야 합니다.

1번 세계 : 벽을 부수지 않고 이동중인 세계
2번 세계 : 벽을 한번 부순 후 이동중인 세계

이를 위해 큐에 현재 좌표와 별개로 현재 상태또한 넣어줘야 합니다. 현재 상태에 따라 각각을 따로 방문체크 해주며 탐색하면 쉽게 해결할 수 있는 문제입니다.

코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

struct Val{
    int x;
    int y;
    int dis;
    int broken;
};

int main(){
    int board[1001][1001] = {};
    bool check[1001][1001][2] = {};

    int destX[4] = { -1, 1, 0,0 };
    int destY[4] = { 0, 0, 1, -1 };

    int n;
    int m;

    cin >> n >> m;

    memset(check, false, sizeof(check));

    for(int i = 0; i < n; i++){
        string line;
        cin >> line;
        for(int j = 0; j < m; j++){
            board[i][j] = line[j] - '0';
        }
    }

    queue<Val> q;
    q.push({ 0, 0, 0 });
    check[0][0][0] = true;

    while(!q.empty()){
        Val node = q.front();
        q.pop();

        if(node.x == m - 1 && node.y == n - 1){
            cout << node.dis + 1;
            return 0;
        }

        for(int i = 0; i < 4; i++){
            Val next = { node.x + destX[i], node.y + destY[i], node.dis + 1, node.broken };

            if(next.x < 0 || next.x > m - 1 || next.y < 0 || next.y > n - 1)
                continue;

            if(next.broken >= 1 && board[next.y][next.x] == 1)
                continue;

            if(check[next.y][next.x][next.broken])
                continue;

            if(board[next.y][next.x] == 1)
                ++next.broken;

            check[next.y][next.x][next.broken] = true;
            q.push(next);
        }
    }

    cout << -1;
}