벽 부수고 이동하기

문제 링크

벽 부수고 이동하기

아이디어

• $(1,1)\to (N,M)$ 으로 가는 최단 경로를 구하는 문제
• 인덱스 값과 좌표 정보를 오인하지 않게끔 주의합시다.
• $N,M\le {10}^3$ 이므로, Naive한 백트래킹으로는 해결할 수 없습니다.
• 최대 $1$개의 벽을 부술 수 있습니다.
  • 이 때, 벽을 부술 경우 board 의 상태 또한 변화하기 때문에, 이를 주의합니다.
  • 1개의 벽을 부술 수 있으므로, board의 상태를 직접 변화시키지 않고 넘어갈 수 있는 통행권 정도의 상태 값을 탐색시에 추가하는 것으로 문제를 쉽게 해결할 수 있습니다.
• 탐색을 진행하면서 벽을 부술 수 있기 때문에, 먼저 방문하였다고 할 지라도 최솟값을 보장할 수 없겠다는 생각을 하였습니다.
  • 탐색 순서를 고려하는 조건이 까다로울 수 있다는 점을 인지하였습니다.
• 최단 경로 가 절대 될 수 없는 조건으로는, 이전에 방문한 좌표에 대한 최단 거리가 현재까지의 최단 거리보다 작거나 같을 경우, 현재의 경로로는 탐색을 진행하는 것이 무의미합니다.
  • 거리가 같을 경우, 탐색을 진행하는 것도 나쁘진 않으나.. 사이클이 발생할 수 있습니다.
  • 저희가 구하고 싶은 것은, 최단 거리를 구성하는 모든 경로들이 아닌 최단 거리의 값입니다.
• 다익스트라를 이용하여 해결해줍니다.
  • 이 때, 벽을 부수고 $(r,c)$ 에 도달하였거나, 벽을 부수지 않고 $(r,c)$ 에 도달한 상태는 서로 다른 상태이므로, 메모이제이션을 할 때 이를 구분하여 정의해줍니다.
  • dist[f][r][c] := f개의 벽을 추가적으로 부술 수 있는 상태에서 (r, c)에 도달하기 위한 최단 거리

소스코드

#include <bits/stdc++.h>
using namespace std;
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
char board[1001][1001];
int dist[2][1001][1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }

    // {ac_dist, r, c, rest}
    typedef tuple<int,int,int,int> tp;

    fill(&dist[0][0][0], &dist[1][1000][1001], 0x3f3f3f3f);
    priority_queue<tp, vector<tp>, greater<>> pq;
    pq.emplace(1, 0, 0, 1);
    dist[1][0][0] = 1;


    while (!pq.empty()) {
        auto [ac_dist, r, c, rest] = pq.top(); pq.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dir[d][0], nc = c + dir[d][1];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (board[nr][nc] == '1' && rest == 0) continue;

            int next_rest = rest - (board[nr][nc] == '1');
            if (dist[next_rest][nr][nc] <= dist[rest][r][c] + 1) continue;
            dist[next_rest][nr][nc] = dist[rest][r][c] + 1;
            pq.emplace(dist[next_rest][nr][nc], nr, nc, next_rest);
        }
    }
    if (dist[0][N - 1][M - 1] == 0x3f3f3f3f && dist[1][N - 1][M - 1] == 0x3f3f3f3f) {
        cout << -1;
    } else {
        cout << min(dist[0][N - 1][M - 1], dist[1][N - 1][M - 1]);
    }
    return 0;
}