[bfs] 벽 부수고 이동하기 (백준 2206번)

 

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?)

 

1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것.

2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다.

(map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.)

 

3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다.

이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자.

벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때,

 

0번 세계에서 0번 세계로 갈 수 있을 것이다. 그러면 count 하면 된다.

0번 세계에서 1번 세계로 갈 수 있을 것이다. 그러면 count 하면 된다.

그리고 1번 세계에서 0번 세계로 갈 수 있을 것이고, 그러면 count 하면 된다.

그리고 1번 세계에서 1번 세계로 가는 경우는 count 해서는 안 된다.

 

단순히 생각하면 1번에서 1번으로 가는 경우를 막으면 되겠지만,

0에서 1로 갔다가 0으로 간 경우 (통과해주면 안 된다.)

(문제 없다고 생각할 수 있겠지만, 이미 0에서 1로 간 시점에서 벽을 부쉈다는 뜻이니 여전히 1이다.)

 

그리고 1에서 0으로 갔다가 다시 1로 가려는 경우 (통과시키면 안 된다.)

이런 것을 어떻게 구분할 것인가, 그런 문제가 생긴다. (*마치 개개인의 전과 유무를 파악하는 것처럼.)

 

말하자면, 한 번 1의 세계로 가면 다시는 돌아올 수 없다는 뜻이다. (애니메이션인가요?)

 

그렇기 때문에

1. 전역 변수마냥 벽을 부순 유무를 체크하는 bool 변수를 만든다. (해봤는데 실패했다.)
2. 방문 여부를 체크하면 2차원 배열을 2개 만들어서 관리한다.

이 둘을 나눠서 생각해볼 수 있는데,

1번은 사실 조금만 생각해봐도 위의 경우의 수를 모두 구분할 수 없는 것을 알 수 있다. (조금?)

(백 트래킹 방식으로 하면 모를까, bfs에서는 무리다, 그리고 dfs로 하면 시간초과가 확정이다.)

 

고로 1번 방식의 전역 변수는 포기해야 한다, 반드시 매개로 넘기는 백 트래킹이어야 할 것이다.

만약 2번 방법을 쓴다고 해보자,

그러면 int visited[1001][1001]을 2개 만드는 것이니 그냥 int visited[1001][1001][2] 라고 선언하자.

(배열의 이름은 그냥 각자 원하는대로 지으면 된다.)

단, 앞서 말한 것처럼 0에서는 0과 1의 세계를 모두 가지만 1에서는 0의 세계로 갈 수 없다는 점 때문에,

0의 세계는 독립적이지만, 1의 세계는 결코 독립적이지 않다는 점, 잊어서는 안 된다.

 

이 말이 무슨 뜻인가 하면, 한 번 벽을 부순 시점에서 int visited[][][ 이 부분 ]은 항상 값이 고정이라는 점.

 

4. queue에 이전에 벽을 부순 적 있는지를 넣어야 한다. (배열을 만들던, dfs로 매개변수를 만들던)

앞서 이미 설명했지만, 몇 번을 강조해도 부족하지 않다, 전역으로 처리하려고 해도 처리할 수 없다.

 

5. 어느 한 칸에 대하여 벽을 안 부술 수 있으면 안 부수고 가는 게 유리하다.

(그리고 부순 횟수가 적을 때만 방문하는 방식... 이 방식을 구현하면 내가 구현한 것보다 좋을 듯하다.)

(자세한 이유는 아래에 표로 나타낸 것 중, 중복해서 방문하는 경우를 보면 된다.)

(근데 이 문제에서만 적용가능한 greedy algorithm이라서 좀 아쉽다.)

 

5 6
000000
011110
010000
010111
100000

(원한다면 입력해서 결과를 비교해봐도 좋다, 질문 코너에서 찾은 test case다.)

 

가로가 6, 세로가 5인 미로가 다음과 같이 있을 때, 최종적인 도착은 아래와 같이 10번째이다.

아래의 두 지도는 0의 세계(벽을 부수지 않은 세계)와 1의 세계(벽을 부순 세계)이다.

가장 왼쪽 위를 (1,1) 도착점을 (5,6) (나는 항상 int y, int x 꼴과 같이 y를 앞에 쓴다, 프로그래밍에선)

라고 할 때,

 

0의 세계는 이해가 갈 것이다.

그런데 1의 세계는 뭐 어떻게 되어 먹은 건지 도저히 모를 수가 있겠는데,

1의 세계의 방문 기록은 0의 세계와 무관하기 때문에 0의 세계에서 지나간 곳도 다시 방문해서 돌아간다.

또한,

(2,2) 지점을 보면 3이라고 되어 있는데, 이건 (2,1) (당시 강조하는데 y축이 2, x축이 1인 지점)에서 간 거다.

 

이 모양 다음에,

이런 모양이 된다.

그리고 더 나아가면,

이런 모양이 되는데, 어디서 어디로 가는지를 잘 봐야 한다.

(1,2) 지점의 2(0)에서 아래 칸으로 내려간 게 아니라, 좌측에서 우측로 간 것이다.

그리다 보면 이런 논리 흐름이 있는데, 앞서 말한 것처럼 1에서 1로 가는 경우를 제외하고는 다 가능해서,

[1]의 세계는 개판이다.

0에서 건너온 놈뿐만 아니라 1에서의 흐름도 있어서, (2,5)처럼 0의 세계가 중첩되는 경우의 수도 있고

(3,5)처럼 0과 1이 같이 있는 경우도 있고 (이 경우는 사실 엄청나게 많다.)

하여간 겹쳐서 보는 것은 사람 할 짓이 못된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
 
int n, m;
int map[1001][1001];
int visited[1001][1001][2];
// bool로 만드는 게 데이터 효율이 높긴 하겠지만, 여기다가 ++연산을 해서 이동 횟수를 기록할 생각이다.
// map에다가 기록해버리면 1이 되는 순간 벽으로 취급될 테니 꼬인다.
 
int xMove[4] = { 0,0,-1,1 };
int yMove[4] = { 1,-1,0,0 };
// 항상 느끼지만, yMove를 입력할 때 나는 상하좌우라고 생각하며 입력하는데,
// 실제 지도는 왼쪽 위가 0,0 또는 1,1로 기준 잡히기 때문에 상하가 뒤집힌다.
// 지금까지 모든 문제를 그리 풀었고 문제 없었지만 인간을 기준으로 한 게 아니라 헷갈리겠다.
 
typedef struct pos
{
    int y;
    int x;
    int breakingWall;
    // 만약 0라면 벽을 1번 부술 수 있는 기회가 있고, 아니면 없다.
    // 생각해보니 이거 백트래킹으로 풀어도 될 거 같은 느낌이 든다. (간질간질)
    // 코드 짤 때 주석달면서 문제를 푸니까, 논리적 흐름이 다 기록되서 훨씬 잘 되는 거 같고,
    // 그리고 마치 대화하는 기분이라 코딩이 재밌다.
    // 이거 완전히 히키코모리, 아싸 새끼 아닐까.
} pos;
 
int bfs(void)
{
    queue<pos> Q;
    visited[1][1][0] = 1;
    Q.push({ 1,1,0 });
 
    while (!Q.empty())
    {
        pos cur = Q.front();
        Q.pop();
 
        if (cur.y == n && cur.x == m) return visited[cur.y][cur.x][cur.breakingWall];
        // 중간에 벽을 부쉈는지 안 부쉈는지 모르니까 cur.breakingWall이 0인지 1인지는 알 수 없다.
 
        for (int i = 0; i < 4; i++)
        {
            pos next;
            next.y = cur.y + yMove[i];
            next.x = cur.x + xMove[i];
            next.breakingWall = cur.breakingWall;
            //            필요한 것은 지금까지 벽을 부쉈는지 유무라 next의 값이 필요하지가 않다.
            //            근데 초기화 안하면 실행이 안되니까 그냥 cur의 해당 값을 넣어줬다.
 
            if (next.y <= 0 || next.y > n || next.x <= 0 || next.x > m) continue;
            if (visited[next.y][next.x][cur.breakingWall]) continue;
            // 벽을 부수고 도달했든 부수지 않고 도달했든 방문한 적이 있으면 continue한다.
            // 이 if문이 매우 매우 매우 중요하다, 노트북에 대고 빨간펜으로 동그라미칠 만큼 중요하다.
 
            // 나는 이 if문을 잘못 작성하는 바람에, 손으로 하나 하나 다 그리는 고생을 해야 했다.
            // if(visited[][][])의 꼴에서 세번째 [] 구간이 cur.breaking이라는 점.
            // 만약 visited[next.y][next.x][0]을 출력한다면 벽을 뚫고 가지 않은 상태로 출력될 것이고
            // 만약 visited[next.y][next.x][1]을 출력한다면 벽을 뚫고 간 경우의 평행세계가 출력된다.
            // ([1]의 세계는, 0으로부터 영향을 받아서, 그냥 보기엔 이해가 안 갈 수도 있을 것이다.)
            
            // 우리는 0에서 0으로 가는 경우, 0에서 1로 가는 경우, 1에서 0으로 가는 경우를 고려해야한다.
            // 문제는 1에서 0으로 가는 경우에는, 여전히 [1]의 세계에 있어야 한다는 점이다.
            // [1]의 세계에 있음은, 1에서 0으로 갔어도 벽을 뚫고 갔던 적이 있음을 나타내야 하기 때문이다.
 
            if (map[next.y][next.x] == 0)
            {
                visited[next.y][next.x][next.breakingWall] = visited[cur.y][cur.x][cur.breakingWall] + 1;
                Q.push({ next.y,next.x,cur.breakingWall });
            }
            if (map[next.y][next.x] == 1 && next.breakingWall == 0)
            {
                visited[next.y][next.x][1] = visited[cur.y][cur.x][cur.breakingWall] + 1;
                next.breakingWall = 1;
                // next.breakingWall + 1인 부분이 차이점이다, 만약 +1을 빼버리면
                // 0에 값이 대입이 될 거고, 아래 Q.push에는 1이 대입이 되어 값 전달을 새로 시작해버린다.
                Q.push(next);
            }
            // dfs였다면 cur.breakingWall 이라는 것 대신에 매개변수를 한 개 더 쳐넣었을 것이다.
            // 이 차이 때문에 백트래킹도 가능할 거라고 생각한 것.
            // 백트래킹이 뭐냐고... 묻는다면, 현재의 진행 상황을 매개변수로 가지고 있어서,
            // 이후의 값들을 탐색할 필요가 없을 경우 탐색 가능한 지점으로 돌아가는 알고리즘이다.
        }
    }
 
    return -1;
    // 이 고생하고도 n, m 지점으로 가지 못했으면 -1을 반환한다, 답이 없다.
}
 
int main(void)
{
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            //            cin >> map[i][j];
            scanf("%1d", &map[i][j]);
        }
    }
 
    cout << bfs();
 
    /*
    cout << endl << endl;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << visited[i][j][0] << "  ";
        }
        cout << endl;
    }
 
    cout << endl;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << visited[i][j][1] << "  ";
        }
        cout << endl;
    }
    */
    // 문제를 찾기 위해서 visited 기록을 모두 출력해봤다.
    // 맞는 코드를, 내 딴에는 고친다고 했던 것이 한 시간을 잡아먹었다.
}

 

예전에 못 푼 문제였는데, 이제는 풀 수 있다.

성장했다.