[백준 2206 - C++] 벽 부수고 이동하기 : BFS

www.acmicpc.net/problem/2206

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을 출력한다.

 

 

풀이

이 문제를 읽고 가장 먼저 할 수 있는 생각은 그냥 2중 loop로 모든 벽을 하나씩 없애 보면서 거기서 bfs를 실행하는 것이다.

그러나 이 경우는 2중 loop는 O(n*m), 그 안에서 실행되는 bfs 역시 O(n*m)이라 전체적으로 O(n^2*m^2)이 돼서 무조건 시간초과가 난다.

 

그래서 생각한 두번째 아이디어는 bfs에 쓰이는 큐에 이전에 벽을 부쉈는지, 안부쉈는지를 저장해서 풀어보았다.

즉 큐에는 {x, y, 이동횟수, 벽 수순지 여부} 네가지 정보가 모두 들어간다.

그러나!!! 틀렸다ㅠ 그것도 5%에서...

 

다시 생각을 해보니 위의 아이디어도 문제가 있었다. 이럴땐 질문 게시판을 활용하자..

www.acmicpc.net/board/view/27386

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

내가 (x, y)라는 좌표애 도달했다고 하자, 그렇다면 여기까지 오는데에 벽을 부수고 왔을 수도 있고, 벽을 부수지 않고 왔을 수도 있다.

만약 벽을 부수고 (x, y)에 도달했다면 (x, y)에서 목적지 까지 가는 길에는 벽을 부술 수 없다.

 

내가 위에서짠 코드는 벽을 부수고 (x, y)에 도달하는 시간이 벽을 부수지 않고 (x, y)에 도달하는 시간보다 빠르다면, 벽을 부수지 않고 오는 경우는 더이상 고려할 수가 없게된다. 이미 (x, y)를 방문한 것으로 체크 했기 때문이다. 그런데 만약 (x, y)까지는 벽을 부수고 오지 않는 방법이 있고 (x, y)에서 목적지 까지는 벽을 부수지 않고 도달할 수 없다면, 내 코드에선 벽을 하나 부수고 도달 할 수 있음에도 불구하고 도달할 수 없는것으로 생각해 버리기 때문이다.

즉, 벽을 부수고 (x, y)에 도달한 경우와 부수지 않고 (x,y)에 도달한 경우 모두 고려할 수 있도록 코드를 수정해 주어야한다.

 

따라서 방문을 확인하는데에 쓰던 2차원 배열 visited[n][m]을 3차원으로 하여 visited[n][m][2]로 두고 visited[n][m][0]에는 부수지 않고 도달한 방문여부를, visited[n][m][1]에는 부수고 도달한 방문여부를 저장한다.

 

오타를 정말 잘 확인해야한다...

for(int i=0; i<4; i++){ 를

for(int i=0; i<n; i++){ 라고 써서 시간초과 오져서 망했었다. 하ㅠㅠㅠ

 

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

char map[1001][1001];
int visited[1001][1001][2];

int X[4] = {1, -1, 0, 0};
int Y[4] = {0, 0, 1, -1};

queue<pair<pair<int, int>, pair<int, int>>> check;   //x, y, cnt, 부숨

int main(void){
    int n, m;
    int x, y, n_x, n_y;
    int cnt;
    int destroy;
    int result= -1;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        scanf("%s", map[i]);
    }
    
    check.push(make_pair(make_pair(0, 0), make_pair(1, 0)));
    visited[0][0][0] = 1;
    
    while(!check.empty()){
        x = check.front().first.first;
        y = check.front().first.second;
        cnt = check.front().second.first;
        destroy = check.front().second.second;
        check.pop();
        //printf("%d %d\n", x, y);
        if(x == n-1 && y == m-1){
            printf("%d\n", cnt);
            return 0;
        }
        
        for(int i=0; i<4; i++){
            n_x = x+X[i];
            n_y = y+Y[i];
            if(n_x < 0 || n_x >= n || n_y < 0 || n_y >= m)
                continue;
            
            if(map[n_x][n_y]=='1' && destroy == 0){
               // printf("%d %d\n", n_x, n_y);
                check.push(make_pair(make_pair(n_x, n_y), make_pair(cnt+1, 1)));
                visited[n_x][n_y][1] = 1;
            }
            else if(map[n_x][n_y]=='0' && visited[n_x][n_y][destroy]==0){
                check.push(make_pair(make_pair(n_x, n_y), make_pair(cnt+1, destroy)));
                visited[n_x][n_y][destroy] = 1;
            }
        }
    }
    printf("%d\n", result);
}