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

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

풀이

기본적으로 (1, 1)부터 (N, M)까지 BFS를 이용해서 최단 거리를 구하면 되는데, 벽을 최대 1번 부술 수 있다는 조건을 처리할 방법을 떠올리는 것이 어려웠다.

BFS의 시작부터 끝까지 벽을 부순 횟수를 가지고 있어야 하는데, 하나의 변수로 이를 관리하기에는 커버하지 못하는 경우가 발생하므로 적절하지 않다. (만약 broken이라는 변수로 벽을 부순 횟수를 0 또는 1로 저장한다면, 어느 시점에서 broken을 1로 만들지 정하기 어렵다.)

따라서 모든 경우를 커버할 수 있도록 dist 배열을 3차원으로 만들어서
dist[x][y][broken]에 현재까지 벽을 부순 횟수가 broken일 때 (1, 1)부터 (x, y)까지의 최단 거리를 저장한다.

현재 칸에서 다음 칸으로 이동하고자 할 때, 가능한 경우는 아래와 같다.

1. 맵의 0칸 - 부수지 않고 이동
   현재 broken 값과 관계 없이, 이전 방문 여부에 따라 이동 가능
2. 맵의 1칸 - 부수고 이동
   현재 broken 값이 0이고, 이전에 방문한 적 없으면 부수고 이동 가능
3. 맵의 1칸 - 부수지 않고 이동하지 않음

코드

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

struct Room {
    int x, y, broken;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<string> grid(N);

    for(int i=0; i<N; i++) {
        cin >> grid[i];
    }

    vector<vector<vector<int>>> dist(N, vector<vector<int>>(M, vector<int>(2, -1)));
    queue<Room> q;

    q.push({0, 0, 0});
    dist[0][0][0] = 1;

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

    while(!q.empty()) {
        auto [x, y, broken] = q.front();
        q.pop();

        int d = dist[x][y][broken];

        if(x == N-1 && y == M-1) {
            cout << d;
            return 0;
        }

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(grid[nx][ny] == '0') {
                if(dist[nx][ny][broken] == -1) {
                    dist[nx][ny][broken] = d + 1;
                    q.push({nx, ny, broken});
                }
            } else {
                if(broken == 0 && dist[nx][ny][1] == -1) {
                    dist[nx][ny][1] = d + 1;
                    q.push({nx, ny, 1});
                }
            }
        }
    }
    
    cout << -1;
    
    return 0;
}

시간복잡도

BFS의 노드는 N×M개, 간선은 최대 4×N×M개이므로 O(NM)이다.

개선점

1️⃣ 정수형 벡터 dist를 사용하는 대신, bool형 배열 visited로 방문 여부, 정수형 변수로 최단 거리를 분리하여 관리한다.

• 알고자 하는 것은 1개의 시작 지점으로부터 1개의 목표 지점까지의 최단 거리이므로 dist 배열에 중간 지점들까지의 거리를 모두 저장할 필요가 없음
• 배열이 연속 메모리 배치로 캐시 적중률이 높은 반면, 벡터는 그렇지 않음
• 정수형 벡터는 4바이트씩 쓰지만, bool형 배열은 1바이트씩 쓰므로 메모리 절감 효과

2️⃣ visited[x][y][broken] 대신, visited[broken][y][x]으로 broken 차원을 앞에 둔다.

• BFS 동안 대부분 broken 값은 고정된 상태에서 상하좌우 인접 칸으로 이동하므로 (x, y)가 연속되면 공간 지역성이 좋아짐