[백준 - 14442] 벽 부수고 이동하기 2 - C++

분류: BFS, 3차원 BFS /

 

문제

문제 링크

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

문제

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

struct xyk {int x, y, k;};
char board[1000][1001];
int dist[1000][1000][11];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M, K; cin >> N >> M >> K;
    int endX = N-1, endY = M-1;
    for(int i=0; i<N; i++) cin >> board[i];

    queue<xyk> Q;
    dist[0][0][0] = 1;
    Q.push({0, 0, 0});
    while(!Q.empty()) {
        xyk cur = Q.front(); Q.pop();
        if(cur.x == endX && cur.y == endY) {
            cout << dist[cur.x][cur.y][cur.k];
            return 0;
        }
        for(int d=4; d--;) {
            int nx = cur.x + dx[d], ny = cur.y + dy[d];
            if(nx<0 || nx>endX || ny<0 || ny>endY) continue;
            int nk = board[nx][ny] == '1' ? cur.k + 1 : cur.k;
            if(nk > K || dist[nx][ny][nk]) continue;
            dist[nx][ny][nk] = dist[cur.x][cur.y][cur.k] + 1;
            Q.push({nx, ny, nk});
        }
    }
    cout << -1;
}

앞서 풀었던 [백준 - 2206] 벽 부수고 이동하기와 [백준 - 1600] 말이 되고픈 원숭이를 합친 문제

이미 풀어본 문제들이라 어렵지 않게 풀 수 있었다. 이번 기회에 이런 유형에대해 조금 정리를 해봤다.

정리한 생각과 새로 알게된 것들을 정리해보자.

 

# 1 X 1 메트릭스인 경우 종료 조건(feet. 재귀함수)

말이 되고픈 원숭이, 벽 부수고 이동하기 첫번째 풀이에서 while문이 `N = 1, M = 1` 인 경우를 해결하지 못해 입력을 받자마자 `N = 1, M = 1`인지 확인하고 종료하는 방법으로 해결했다.

while문이 시작점과 도착점이 같은 경우를 걸러내지 못하는 이유는 시작점에 방문 표시를 하고 BFS를 시작하는데 BFS에서 방문 표시가 된 좌표를 다시 방문하지 않아 절대로 도착점(= 시작점)에 도달하지 못한다. 시작점과 도착점이 같은데 -1이 출력된다.

벽 부수고 이동하기 두번째 풀이에서는 이와 같은 문제를 큐에서 뽑자마자 도착점인지 검사하는 방법으로 해결했다.

재귀 함수에서 종료 조건 검사를 재귀호출 전에 하면 콜스택 하나를 아낄 수 있지만 재귀함수 실행되자 마자 종료조건을 검사하면 코드가 간결해진다.

이와 마찬가지로 큐에서 뽑자마자 종료조건을 검사하면 시작점과 도착점이 같은 경우에도 잘 작동하지만 답이 나왔음에도 남은 BFS 사이클을 모두 돈다. 

N이 아주 크지 않은 이상 성능에는 큰 차이가 없으므로 앞으로는 쿄에서 뽑자마자 종료조건을 검사하는 방향으로 코드를 작성할 예정이다.

 

# Structure Binding Declartion (since C++ 17)

다른 사람의 코드를 보다가 충격적인 문법을 봤다.

auto [x, y] = Q.font();

항상 C++을 쓰며 JS/TS의 destructuring assignment같은 기능없나 하고 찾아보곤 했었는데 있었다.

C++ 17 부터여서 버전을 보고 잘 사용해야겠지만 행복하다.

cppreference: Structure Binding Declartion