[C++ 백준 풀이][Gold IV] 2206번 : 벽 부수고 이동하기 (조건이 추가된 BFS)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 문제인 2206번 : 벽 부수고 이동하기의 풀이 코드와 해설을 다룹니다.

 

문제의 난이도는 Solved.ac 기준 난이도 Gold IV에 해당합니다.

문제에 필요한 알고리즘에 대한 배경지식은 BFS, 큐(+ 페어) 정도가 있습니다.

그럼 바로 풀이 시작하겠습니다.

 

 

2206번 : 벽 부수고 이동하기

 

N×M 크기의 맵을 입력받았을 때, 벽을 한 개까지 부술 수 있다고 가정할 때 1행 1열에서 N행 M열까지 가장 빠르게 이동하는 최단 거리를 구하는 문제입니다.

최단 거리를 구하므로 BFS를 사용함을 예상할 수 있습니다만, 중요한 포인트인 벽을 부수는 부분을 어떻게 처리할 것인지가 시간 초과를 좌우하는 관건이 될 것입니다.

예제의 경우에는 1행 2열의 벽을 부술 경우 15의 최단 거리로 N행 M열까지 이동할 수 있음을 확인할 수 있습니다.

그럼 풀이 코드를 작성해보겠습니다.

 

 

↓ 사용 가능한 동일 풀이 코드는 아래 접은 글에 작성되어 있으니 참고해주세요.

#include <iostream>
#include <queue>
using namespace std;

int N, M, breakable;
int Map[1005][1005], visit[1005][1005][2], unit[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
queue<pair<pair<int, int>, int>> Q;

int BFS() {
    int x, y, next_x, next_y;
    Q.push({{1,1},1});
    visit[1][1][1] = 1;
    while(!Q.empty()) {
        y = Q.front().first.first;
        x = Q.front().first.second;
        breakable = Q.front().second;
        Q.pop();
        if(y == N && x == M) return visit[y][x][breakable];
        for(int i=0; i<4; i++) {
            next_y = y + unit[i][0];
            next_x = x + unit[i][1];
            if(next_y>=1 && next_y<=N && next_x>=1 && next_x<=M) {
                if(Map[next_y][next_x] && breakable && !visit[next_y][next_x][breakable-1]) {
                    visit[next_y][next_x][breakable-1] = visit[y][x][breakable]+1;
                    Q.push({{next_y, next_x}, breakable-1});
                }
                else if(!Map[next_y][next_x] && !visit[next_y][next_x][breakable]) {
                    visit[next_y][next_x][breakable] = visit[y][x][breakable]+1;
                    Q.push({{next_y, next_x}, breakable});
                }
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> M;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) scanf("%1d", &Map[i][j]);
    cout << BFS();
}

 

정답률이 낮은 것을 발견하셨다면, 벽을 제거하는 과정을 브루트포스 알고리즘으로 찾으면 안된다는 것을 알아야 합니다.

이 문제의 알고리즘 분류가 브루트포스로 되어있는 것은 BFS 과정에서의 브루트포스를 의미하는 것이지, 모든 벽을 한 번씩 제거해보고 수행하라는 이야기가 아니었습니다.

그래서 저도 생각을 짧게 했다가 막상 코드를 돌려보니 시간이 오래 걸려서 안될 것임을 직감했습니다.

 

그래서 다른 분들의 풀이 아이디어를 참고를 했는데, 바로 벽을 부수는 것까지 visit 배열에 저장해서 벽을 부순 여부를 기록하는 것입니다.

따라서 queue 또한 pair가 아닌 이중 pair를 사용해서 breakable 변수(벽을 아직 부술 수 있으면 1, 아니면 0)를 같이 저장하도록 하였습니다.

그리고 23행의 조건문 부분이 가장 중요한데, 해당 인접 방향이 벽임과 동시에 벽을 아직 부술 수 있으면 기회를 소모하고 해당 칸으로 이동하는 것입니다.

27행의 조건문에서도 breakable이 unavailable 상태여야 이동이 가능하다와 같은 조건문을 사용하는 것은 틀리기 때문에, 실수를 하지 않도록 주의합니다.

 

그 외에 나머지 부분들은 일반적인 BFS 문제의 풀이와 같습니다.

N행 M열에 도달하면 현재까지 기록된 거리를 리턴하고, 만약 BFS가 끝났는데도 도달하지 못했다면 -1을 리턴해줍니다.

메인 함수에서는 리턴받은 값을 출력해주기만 하면 최단 거리가 됩니다.

 

 

채점을 해보면 124ms의 시간으로 정답 처리가 되었음을 확인할 수 있습니다.

간혹 풀이를 하다가 메모리 초과가 발생하는 경우가 있는데, 그것은 배열 때문이 아니라 큐 때문일 가능성이 높습니다.

큐에서 breakable과 map 변수에 집중한 나머지 visit 변수를 체크하지 않는다면 왔던 경로도 다시 큐에 대입을 해버리기 때문에 기하급수적으로 큐의 데이터 수가 늘어나 메모리 초과가 발생하게 됩니다.

따라서 메모리 초과를 발생시키지 않도록 기초적인 실수를 하지 않아야 합니다.