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

백준 2206번

벽 부수고 이동하기

2차원 배열로는 해결할 수 없는 문제였다. (어찌저찌 어거지로 가능은 하지만…너무 어렵다)

3차원 배열을 사용해 두 개의 경로를 관리해야 한다.

1. 최단거리를 찾아야 하기 때문에 이미 방문한 곳은 다시 방문할 필요가 없다.
2. 방문 여부를 확인할 때, 벽을 이미 뚫은 경우와 아직 벽을 뚫어본 적이 없는 경우를 나눠 관리해야 한다.

따라서 방문 여부를 기록하는 visited 배열을 만들 때 두 가지 버전을 만들어야 한다.

처음 시작은 벽을 뚫지 않은 경우의 visited 배열에서 시작해 기록해나간다.

만약 중간에 벽을 뚫는다면, 벽을 뚫은 visited 배열로 넘어가야 한다.

Queue에는 «좌표>,<벽 부수기="" 가능="" 여부="">>를 담아야 한다.

벽 부수기 가능 여부를 하나의 모드로 보면 될 것 같다.

벽을 부수지 않은 경우 = 모드 0

벽을 부순 경험이 있는 경우 = 모드 1

로 두고 풀었다.

몇 번 이동했는지는 level 배열을 사용해 관리한다. Level 배열도 마찬가지로 두 가지 버전을 생성해야 한다.

시작점에서 출발해 다음 방문 가능한 곳을 탐색할 때,

1. 만약 다음에 방문할 곳이 0이고(벽이 아니고) 현재 모드에서 방문한 적이 없는 곳이라면

   (벽이 아니기 때문에 단순 방문 여부로 판단한다.)

   1. 벽을 뚫었는지 여부에 관계 없이 방문 가능한 곳이다.
   2. Queue에 좌표와 현재 모드를 push 한다.
   3. 몇 번 이동했는지 현재 모드의 level 배열에 기록하고, 현재 모드의 visited 배열에 방문 여부를 기록한다.

2. 만약 다음에 방문할 곳이 1이고 현재 벽을 부순 적이 없을 때

   (전에 벽을 부순 적이 있다면 벽을 만났을 때 부술 수 없기 때문에 할 수 있는게 없다.

   1. Queue에 좌표와 함께 현재 모드 (=1, 방금 벽을 부쉈기 때문이다.)를 push 한다.
   2. level 배열을 업데이트 한다.

처음에는 이렇게 두 가지 버전을 만들지 않고 하나의 2차원 배열로 문제를 해결하려고 했는데, 이 경우 벽을 부순 경우의 경로와 그렇지 않은 경우의 경로들이 서로 영향을 주고 얽히고 얽혀 문제를 해결하기 어려워진다.

위와 같이 동작할 경우 두 가지 경우가 잘 관리가 되는데

• 이렇게 하면 벽을 뚫은 경우와 뚫지 않은 경우 두 가지의 경로만 관리할 수 있는 것 아닌가?
• 특정 위치에서 벽을 뚫었다면, 그 뒤에서 벽을 또 뚫어야 갈 수 있는 경로에서는 어떡하나?

라는 궁금증이 생겼고 이해가 가지 않았다.

하지만 다음 예제를 직접 손으로 써보며 따라해보니 이해가 되었다.

정답 : 15 (오답 : 9)

5 5
00000
11101
00001
01111
00010

코드가 동작하며 거친 포인트들은 다음과 같다.

0 1 from 0 0 Mode is 0 // 0,0 에서 0,1로 이동했고, 모드는 0이다. (벽을 부수지 않았다.) 1 0 from 0 0 Mode is 1 // 0,0 에서 1,0으로 이동했고, 모드는 1이다. (벽을 부쉈다.) 0 2 from 0 1 Mode is 0 1 1 from 0 1 Mode is 1 2 0 from 1 0 Mode is 1 0 0 from 1 0 Mode is 1 0 3 from 0 2 Mode is 0 1 2 from 0 2 Mode is 1 2 1 from 1 1 Mode is 1 0 1 from 1 1 Mode is 1 3 0 from 2 0 Mode is 1 0 4 from 0 3 Mode is 0 1 3 from 0 3 Mode is 0 1 3 from 1 2 Mode is 1 2 2 from 1 2 Mode is 1 0 2 from 1 2 Mode is 1 4 0 from 3 0 Mode is 1 1 4 from 0 4 Mode is 1 1 4 from 1 3 Mode is 1 2 3 from 1 3 Mode is 0 1 2 from 1 3 Mode is 1 2 3 from 1 3 Mode is 1 0 3 from 1 3 Mode is 1 4 1 from 4 0 Mode is 1 0 4 from 1 4 Mode is 1 2 4 from 2 3 Mode is 1 3 3 from 2 3 Mode is 1 2 2 from 2 3 Mode is 0 4 2 from 4 1 Mode is 1 3 2 from 2 2 Mode is 1 2 1 from 2 2 Mode is 0 1 2 from 2 2 Mode is 1 3 1 from 2 1 Mode is 1 2 0 from 2 1 Mode is 0 1 1 from 2 1 Mode is 1 3 0 from 2 0 Mode is 0 1 0 from 2 0 Mode is 1 3 1 from 3 0 Mode is 1 4 0 from 3 0 Mode is 0 4 1 from 4 0 Mode is 0 4 2 from 4 1 Mode is 0 3 1 from 4 1 Mode is 1 4 3 from 4 2 Mode is 1 3 2 from 4 2 Mode is 1 4 4 from 4 3 Mode is 1

그림으로 나타내면 다음과 같다.

주황색, 초록색, 보라색, 형광색 등은 길이 1 만에 모두 실패한 경로들이다.

빨간색과 파란색은 꽤 오래 버틴 경로인데, 빨간색은 처음부터 벽을 부시고 지나갔기 때문에 모드 1로 경로가 기록되었고, 파란색은 모드 0으로 벽을 부시지 않고 0을 찾아간 경로이다.

다만 한 가지 유의해야 할 점은, 모드 1(벽은 부순 경우의 경로)은 유일하지 않다는 것이다.

이미 1인 상태에서 지나갔더라도 현재 내가 벽을 부술 수 있는 능력이 있다면, 이전에 다른 경로가 부수고 지나갔던 벽이더라도 다시 부수고 지나갈 수 있다.

즉, 각 모드 1에서는 각 경로가 독립적으로 관리되는데, 그 과정을 좀 멀리서 보면 다음 그림과 같다.

모드 0으로 지나가는 경로들은 아직 벽을 부술 수 있는 가능성이 있기에 계속해서 주변 벽들을 부숴보면서 확인한다. 첫 시작점인 (0,0)에서는 아랫 벽을 부숴보았는데 잘 지나갔기 때문에 계속해서 경로를 찾아나가고 있다. (빨간색)

그 외에는, 파란색 경로, 즉 벽을 부수지 않고 지나가는 경로에서 주변 으로 벽을 부수고, 혹은 부수지 않고 갈 수 있는 모든 길을 확인한다. 다만 모드 0에서는 방문 여부를 확인하기 때문에 모드 0인 경로는 독립적이지 않게 된다.

어차피 정답인 최단거리 경로는 정해져 있다면,

• 벽을 먼저 뚫고 지나간 경로가 막히더라도 아직 벽을 뚫지 않은 경로가 나중에 벽을 부술 수 있는 상태로 지나가며 막힌 곳을 지나갈 거고
• 벽을 먼저 뚫고 지나간 경로가 목적지에 도착했다면 그 경로가 벽을 부순 경로가 되기 때문에 최단 거리 경로가 된다.

3차원 배열을 만들어 경로를 두 가지로 관리하는 방법을 생각해내지 못하면 상당히 어려운 것 같다.

벽을 부쉈는지 여부를 확인하는 배열을 따로 만들어서 해봤지만, 위에 있는 예시가 반례가 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <tuple>

using namespace std;
// Total map
int arr[1001][1001] = {0,};
// visited [y][x][0] : Route without breaking the wall yet.
// visited [y][x][1] : Route with breaking the wall.
bool visited[1001][1001][2]={false,};
// level [y][x][0] : level for non-breaking route.
// level [y][x][1] : level for wall-breaked route.
int level[1001][1001][2] = {0,};

int x_iter[4] = {1,0,-1,0};
int y_iter[4] = {0,1,0,-1};
int main(){
    int height, width;
    cin >> height >> width;
    //Map input
    for(int i=0;i<height;i++){
       string tmp;
       cin >> tmp;
       for(int j=0;j<width;j++){
           arr[i][j] = tmp[j]-'0';
       } 
    }

    // make queue and push starting position
    queue<tuple<int,int,int> > q;
    q.push(make_tuple(0,0,0));
    visited[0][0][0] = true;
    level[0][0][0] = 1;
    
    while(!q.empty()){
        tuple<int,int,int> cur = q.front();
        q.pop();

        int cur_y = get<0>(cur);
        int cur_x = get<1>(cur);
        int breachMode = get<2>(cur);
				// exit if destination
        if(cur_y == height-1 && cur_x == width-1){
            cout << level[cur_y][cur_x][breachMode] << endl;
            return 0;
        }
        
        for(int i=0;i<4;i++){
            int y = cur_y + y_iter[i];
            int x = cur_x + x_iter[i];
            if(y >=0 && y <height && x >=0 && x < width){
                 //if not wall and not visited
                if(arr[y][x]==0 && visited[y][x][breachMode] == false){ 
                    q.push(make_tuple(y,x,breachMode));
                    visited[y][x][breachMode] = true;
                    level[y][x][breachMode] = level[cur_y][cur_x][breachMode] + 1;
                }
                else{
                    //if wall and able to break the wall
                    if(arr[y][x]==1 && breachMode == 0){
                        q.push(make_tuple(y,x,1));
                        visited[y][x][1] = true;
                        level[y][x][1] = level[cur_y][cur_x][breachMode] + 1;
                    }
                }
            }
        }
    }
    cout << "-1\n";

}