[BOJ] 2206번 - 벽 부수고 이동하기

문제

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

제한

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

4 4
0111
1111
1111
1110

예제 출력 2

-1

출처

www.acmicpc.net/problem/2206

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

접근 방법

가중치가 없는 최단 경로를 찾기 위해선 BFS로 접근하는 것이 가장 좋을 것이라 생각하여 BFS로 접근하였다.
문제 조건에 따라 처음에는 1로 표시 된 부분들에 대해 하나 씩 0으로 마킹하여 BFS를 돌리는 방식으로 생각을 해보았으나
이럴 경우 BFS탐색 마다 O(NM)이 소요되고, 벽이 최대 NM개가 존재할 수 있으므로 최악의 상황일 경우 O(NM*NM)이 소요된다.
N과 M의 범위가 1000이하이므로 최악의 경우 10^12의 시간이 소요되게 된다.
대략 10^8을 연산하는데 1초가 걸린다고 주먹구구식으로 생각해 보았을 때 이 시간으로는 도저히 풀 수 없을 것이라 판단하였다.

위 문제에서 BFS를 한번만 수행하면서 최단경로를 찾는 방법이 무엇일까?
핵심은 바로 BFS에서 방문 처리를 할 때, 이 경로가 벽을 부수고 도착한 경우인지 벽을 부수지 않고 도착한 경우인지를 구분하여 표시하는 것에 있다.
즉 3차원 배열로 visited 배열을 vistied[벽을 부수고 왔는지?][y][x] 여부를 확인하는 것이 핵심이다.

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class POINT{
public:
    int y,x, dist, block;
};
// vistied 배열을 3차원 으로 만들자.
// 벽돌을 깨고 방문한 특정 좌표와 벽돌을 깨지 않고 방문한 특정 좌표는 다르게 취급해야함
char board[1001][1001];
bool visited[2][1001][1001];
int N,M;
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int BFS(int sy, int sx){
    queue< POINT > Q;
    visited[0][0][0] = visited[1][0][0] = true;
    Q.push({0,0, 1,1});

    while(!Q.empty()){
        POINT np = Q.front(); Q.pop();
        if( np.y == N-1 && np.x == M-1 )
            return np.dist;

        for(int i=0; i<4; i++){
            int ny = np.y + dir[i][0];
            int nx = np.x + dir[i][1];
            if( ny < 0 || ny >= N || nx < 0 || nx >= M ) continue;
            if( visited[np.block][ny][nx] ) continue;

            // 깰 수 있는 블록 수가 없을 경우에는 1로 이동을 못한다.
            if( np.block == 0 && board[ny][nx] == '1' ) continue;

            if( np.block > 0 && board[ny][nx] == '1' ){
                visited[np.block][ny][nx] = true;
                Q.push({ny,nx, np.dist+1, np.block-1});
            }
            if( board[ny][nx] == '0' ){
                visited[np.block][ny][nx] = true;
                Q.push({ny,nx,np.dist+1,np.block});
            }
        }
    }

    return -1;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> board[i][j];
        }
    }

    int answer = BFS(0,0);
    cout << answer;
    return 0;
}