벽 부수고 이동하기(백준 2206)

(출처) https://www.acmicpc.net/problem/2206

부수는 것만 아니면 그냥 단순한 BFS 문제

해당 문제는 어느 두 점의 최단경로를 구하는 평범한 BFS 문제처럼 보였지만 특이하게도 중간에 벽을 단 한 번 부실 수 있다는 조건이 붙어 있었다.

따라서 BFS로 최단거리를 구해나갈 때 벽을 부수기 전, 벽을 부순 후 2가지의 상황을 나누어서 구해나가면 되지 않을까 생각해 보았다.

즉 BFS로 구한 답을 보관해놓는 기존의 Dist 배열(시작점으로부터 특정 정점까지의 최단경로를 보관해놓는 배열, 이 Dist배열을 통해 특정 정점에 대한 방문 여부도 확인할 수 있다)에 벽에 관련된 2가지 상황을 세분화 시켜서 탐색을 진행시켜 보기로 하였다.

( EX :
Dist[0][1][0] == 시작점으로부터 (0,1) 좌표까지 벽을 부수고 난 상황에서의 최단거리
Dist[0][1][1] == 시작점으로부터 (0,1) 좌표까지 벽을 부수지 않은 상황에서의 최단거리

Dist 배열은 최초 모두 INF 값으로 초기화하여 사용할 예정
)

위 같은 방식으로 탐색을 전부 진행시키고 나서 마지막에는 Dist[N-1][N-1][0] 과 Dist[N-1][N-1][1] 의 값 중에 더 작은 값을 선택하여 출력시켰다.

시간복잡도

입력으로 주어지는 맵의 크기는 1000^2로 최대 백 만개이다.

따라서 BFS의 큐에는 최대 백만 개의 노드가 들어가게 된다.

그런데 이 문제는 특정 좌표를 나타내는 하나의 노드가 벽을 부순 후의 노드와 벽을 부수기 전의 노드로 나누어진다.
(하나의 좌표에 2가지의 상태가 존재할 수 있다.)

따라서, 벽을 부순 후 노드 백만 개 + 벽을 부수기 전 노드 백만 개 = 최대 2백만 개의 노드가 큐에 들어갈 수 있다고 볼 수 있다.

이때 큐에 들어간 노드 하나당 내부에서 총 4번의 움직임 검사(상하좌우)를 실시하므로, 2백만 * 4 = 최대 8백만 정도의 계산 횟수가 발생할 수 있다고 예측할 수 있다.

이 정도라면 주어진 시간제한 2초면 충분히 해결할 수 있어 보인다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 987654321;

int N, M;
vector<vector<int>> map;
int D[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
struct Point {
    int row, col, dist, hammer_chance;
};

vector<vector<vector<int>>> bfs() {
    vector<vector<vector<int>>> dist(N,vector<vector<int>>(M,vector<int>(2,INF)));
    Point start = {0,0,1, 1};
    queue<Point> q;
    q.push(start);
    dist[0][0][1] = 1;
    while(!q.empty()) {
        Point here = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int dy, dx;
            int hammer = here.hammer_chance;
            dy = here.row + D[i][0];
            dx = here.col + D[i][1];
            if(dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
            if(map[dy][dx] == 1) {
                if(!here.hammer_chance) continue;
                hammer = 0;
            }
            if(dist[dy][dx][hammer] > here.dist + 1) {
                dist[dy][dx][hammer] = here.dist + 1;
                Point next = {dy, dx, here.dist + 1, hammer};
                q.push(next);
            }
        }
    }
    return dist;
}

int main() {
     cin >> N >> M;
     map = vector<vector<int>> (N, vector<int>(M,-1));
     for(int i = 0; i < N; i++) {
         for(int j = 0; j < M; j++) {
             int temp;
             scanf("%1d", &temp);
             map[i][j] = temp;
         }
     }
    vector<vector<vector<int>>> dist = bfs();
    int result = min(dist[N-1][M-1][0], dist[N-1][M-1][1]);
    if (result == INF) result = -1;
    cout << result << endl;
    return 0;

}