BOJ - 2206 벽부수고 이동하기

https://www.acmicpc.net/problem/2206

경로구하기 문제이다.

우선 최단경로를 구하는 거기 때문에 bfs를 생각해 볼 수 있다.

이제 벽을 뚫는 걸 생각해야 하는데,

처음 생각했을때, 벽을 하나씩 부수는 경우의 수를 생각해봤다.

그런데, 문제의 조건에서 n <= 1000, m <= 1000 이라는 조건이 있기 때문에

벽을 하나씩 부순다면 1000 * 1000 = 100만 을 기본으로 깔고

탐색 1000 * 1000 = 100만. 100만 * 100만 이라는 말도 안되는 시간복잡도가 나오기 때문에 다른 방법을 생각해보기로 했다.

두번째로 생각한 방법은 벽을 만날때 이걸 뚫고 가고, 이 뚫는 횟수를 1번까지만 허용하는 거다.

그래서 보통 큐에 y좌표, x좌표만 저장하는데 거기다가 추가로 지금까지 벽을 몇개 뚫었나도 저장했다.

그리고 1번까지만 벽을 뚫을 수 있게 했다.

(여기까지의 코드: https://www.acmicpc.net/source/share/0a8bddd750da47ca9db6cdc8dcb78c23)

그런데 답이 틀려서, 왜그럴까 생각해보다가 질문게시판을 들어갖고, 반례와 함께 visited에 3차원을 써야된다는 걸 알게됬다.

반례

6 5
00000
11110
00000
01111
01111
00010

ans : 18

정답코드

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1004][1004];
int visited[1004][1004][2];
string s;
int dirY[4] = {1, -1, 0, 0};
int dirX[4] = {0, 0, 1, -1};
struct str
{
    int y;
    int x;
    int b;
};
int inf = 987654321;
int mn = inf;

void bfs()
{
    queue<str> q;
    q.push({0, 0, 0});
    visited[0][0][0] = 1;

    while (q.size())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curB = q.front().b;
        int curD = visited[curY][curX][curB];
        q.pop();

        if (curY == n - 1 && curX == m - 1)
        {
            mn = min(mn, curD);
            continue;
        }

        for (int i = 0; i < 4; i++)
        {
            int nextY = curY + dirY[i];
            int nextX = curX + dirX[i];
            if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < m && (!visited[nextY][nextX][curB] || curD + 1 < visited[nextY][nextX][curB]))
            {
                if (a[nextY][nextX] == 1)
                {
                    if (curB < 1)
                    {
                        visited[nextY][nextX][curB + 1] = curD + 1;
                        q.push({nextY, nextX, curB + 1});
                    }
                }
                else if (a[nextY][nextX] == 0)
                {
                    visited[nextY][nextX][curB] = curD + 1;
                    q.push({nextY, nextX, curB});
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            a[i][j] = s[j] - '0';
        }
    }

    bfs();

    if (mn >= inf)
    {
        cout << -1 << "\n";
    }
    else
    {
        cout << mn << "\n";
    }
    return 0;
}

/*
5 5
00000
11110
00000
01111
00000

9

6 5
00000
11110
00000
01111
01111
00010


*/

++ 사실, 2번째 틀리고 나서 생각할 때, 얼핏 3차원 배열을 생각하긴 했었다. 혹시 벽 부순것도 visited에 저장을 해줘야하나? 하고

그런데, 막연히 이렇게 하면 되지않을까 생각만 떠오르고, 그렇게 해야되는 이유가 떠오르지 않아 그냥 안하고 넘어갔었는데, 너무 아쉬움이 남는다. 얼마전에 풀었던 숨바꼭질 문제가 생각나기도 했고. 그래도 어쨌든 내가 안한거고, 타당한 이유를 떠올리지 못했으니 받아들여야겠다. 실력을 더 키워야지.

그래서 3차원 배열을 사용해야 하는 이유가 뭐냐면, 벽을 부수고 간 것이 먼저 도착한 경우 때문이다. 이게 무슨말이냐면

00000
11110
00000
01111
01111
00010

 

를 봤을 때, 정답에 도착하려면 마지막 행 3번째 인덱스에 있는 1(벽)을 부수고 들어가야 한다.
그런데 2차원 배열 visited로 하고, 벽을 뚫는 정보를 큐에 저장하기만 했다면,

if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < m && (!visited[nextY][nextX] || curD + 1 < visited[nextY][nextX]))

이 조건때문에 마지막행 3번째 인덱스까지 가지 못한다. 마지막 행 3번째 인덱스까지 가려면 [2][0]을 반드시 거쳐야 하는데, 여기서 벽을 뚫고 가는게 훨씬 빠르고 (벽 안뚫으면 11번, 뚫으면 3번이면 됨), 단순히

(!visited[nextY][nextX] || curD + 1 < visited[nextY][nextX]))

라는 조건으로는 벽을 안뚫고 돌아가는 경우는 걸러진다.

그런데 마지막행 3번째 인덱스에서 벽을 뚫으려면, 위에서 벽을 뚫으면 안된다.
이때까지는 벽을 안뚫고 아껴두며 마지막행 3번째 인덱스까지 간 경우에만 도착할 수 있는 것이다.
그래서 visited를 삼차원 배열로 visited[n][m][k] 로 만들어서, [n][m]까지 k(벽을 뚫었나, 안뚫었나)인 경우의 최소경로로 표현해줄 수 있다.
그러니깐 n m까지의 최소 경로인데, 벽을 안뚫었을 때의 최소경로, 벽을 뚫었을 때의 최소경로로 표현해주는 거다.
위 반례로 예시를 들면
[2][0]에 도착할 때 2차원으로만 하면 그냥 [2][0]에 도착한 최소경로만 담을 수 있겠지만
3차원으로 하면 [2][0][0] = 11 (벽을 안뚫었을때 [2][0]에 도착하는 최소경로), [2][0][1] = 3 (벽을 뚫었을 때 [2][0]에 도착하는 최소경로)로 각각 표현해줄 수 있고,
여기서 벽을 뚫었을 때의 경우로 계속 진행하면 마지막행 3번째 인덱스에서 막힐 것이고,
벽을 안뚫었을 때의 경우로 계속 진행하면 마지막행 3번째 인덱스에서 벽을 뚫고 도착할 수 있다.

최근에 이런 문제들(경우의 수도 visited에 저장하는)을 몇개 풀었었느데,, 너무 아쉽다... 다음에 더 잘하자!!

도움이 되는 질문게시판 글
https://www.acmicpc.net/board/view/145236