Baekjoon 2206번 벽 부수고 이동하기

문제

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

걸린 시간

02 : 00 : 21 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
int maze[1001][1001];
int visited[1001][1001][2];

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int bfs(){
    queue<pair<pair<int, int>, bool>> q;
    q.push(make_pair(make_pair(1, 1), false));
    visited[1][1][0] = 1;
    int depth = 0;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            auto tmp = q.front();
            auto loc = tmp.first;
            int y = loc.first;
            int x = loc.second;
            q.pop();
            // 목표 지점 도착
            if(y == n && x == m)
                return depth;
            // 상하좌우
            for(int j = 0; j < 4; j++){
                int ny = y+dy[j];
                int nx = x+dx[j];
                bool bore = tmp.second;
                if(1 <= ny && ny <= n && 1 <= nx && nx <= m){
                    if((!bore || maze[ny][nx] == 0) && !visited[ny][nx][bore]){
                        if(maze[ny][nx] == 1)
                            bore = true;
                        visited[ny][nx][bore] = 1;
                        q.push(make_pair(make_pair(ny, nx), bore));
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int y = 1; y <= n; y++)
        for(int x = 1; x <= m; x++)
            scanf("%1d", &maze[y][x]);
    printf("%d\n", bfs());
    return 0;
}

목적지까지 최단 경로를 찾는 bfs 문제이다. 맵의 크기가 M*N 크기이므로 복잡도는 O(MN). 여기서 하나의 벽을 부수고 지나갈 수 있다는 조건이 추가된다.

제일 먼저 벽의 정보를 따로 저장해두고 하나씩 지워가며 매번 bfs 를 수행하는 고지식한 방법이 있다. 이는 벽의 개수가 0개에서 최대 M*N개가 될 수 있으므로 시간초과가 발생하게 된다.

제한시간안에 문제를 통과하기 위해선 조금 더 똑똑한 방법이 필요하다. 큐에 벽을 뚫었는지를 나타내는 변수를 추가로 두어 벽을 만나면 최대 한번 부수고 지나갈 수 있도록 했다.

하지만 이 방법에는 수많은 반례가 존재했다.

4 4
0000
1110
1111
1110

정답 : 7
출력 : -1

대표적으로 위의 반례에서 (3, 4) 위치의 벽을 뚫고 지나가면 목적지에 도달할 수 있지만 -1 이 출력된다. 디버깅을 통해 찾은 원인은 (2, 3) 위치에서 벽을 뚫고 지나온 좌표가 (1, 4) 위치로부터 온 좌표와 중복되었기 때문이였다.

이에 대한 해결책으로 벽을 뚫은 적이 없는 좌표를 먼저 진행시도록 알고리즘을 설계해 보았지만 또 다른 반례가 존재했다. 이런 식으로는 문제를 해결할 수 없을 것 같아 결국 질문 게시판에서 도움을 구했고 방문 배열을 다르게 사용해보라는 핵심적인 힌트를 얻었다.

기존 방문 배열을 3차원으로 바꾸어 벽을 부수고 진행한 경로와 그렇지 않은 경로를 나누면 중복 문제가 해결된다.