[백준 9376번] [Dijkstra] 탈옥

Approach

문제에서 열어야하는 문의 최솟값을 물어보고 있고, 정점과 정점 사이에 이동할 때 벽의 개수가 가중치라고 생각해보면 최단경로(거리)문제로 치환해서 풀 수 있다는 것을 눈치챌 수 있다.

 

문제에서 예시로 들어준 것을 잘 분석해보면, 2명의 죄수가 바깥으로 나가기 위한 최단경로와 관련이 있다는 것을 알 수 있다. 하지만, 벽을 중복해서 부술 수 있다는 점 때문에 단순하게 다익스트라로는 위 문제를 쉽게 해결할 수 없게 된다. 추가적으로 문제를 더 고민해보면, 결국 모든 상황에서 상근이가 바깥에서 안으로 들어오는 것과 2명의 죄수가 바깥으로 나가기 위한 최단경로는 한 점에서 만날 수 밖에 없다는 점을 착안하면 결국 3번의 최단거리의 합에서 벽일 경우 중복을 제거하기 위해 2를 빼주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
char MAP[105][105];
int dist[3][105][105];
pii pt[3];
const int INF = 2000000000;

int main() {
    fastio;
    int t;
    cin >> t;
    for(int test_num = 1; test_num <= t; ++test_num){
        fill(&MAP[0][0], &MAP[104][105], '.');
        pt[0] = {0, 0};
        int h, w;
        cin >> h >> w;
        h++, w++; // 강제적으로 1칸씩 밀음
        bool chk = false;
        for(int i = 1; i <= h - 1; i++){
            for(int j = 1; j <= w - 1; j++){
                cin >> MAP[i][j];
                if(MAP[i][j] == '$'){
                    if(!chk){
                        pt[1] = {i, j};
                        chk = true;
                    }
                    else pt[2] = {i, j};
                }
            }
        }
        fill(&dist[0][0][0], &dist[2][104][105], INF);

        for(int l = 0; l < 3; l++){
            int x, y;
            tie(x, y) = pt[l];
            priority_queue<tiii, vector<tiii>, greater<tiii> > pq;
            pq.push({0, x, y});
            dist[l][x][y] = 0;
            while(!pq.empty()){
                int cur_cost, cur_x, cur_y;
                tie(cur_cost, cur_x, cur_y) = pq.top();
                pq.pop();
                if(dist[l][cur_x][cur_y] < cur_cost) continue;
                for(int i = 0; i < 4; i++){
                    int dx = cur_x + move_x[i];
                    int dy = cur_y + move_y[i];
                    if(dx < 0 || dx > h || dy < 0 || dy > w || MAP[dx][dy] == '*') continue;
                    if(cur_cost + ((MAP[dx][dy] == '.') ? 0 : 1) < dist[l][dx][dy]){
                        dist[l][dx][dy] = cur_cost + ((MAP[dx][dy] == '.' || MAP[dx][dy] == '$') ? 0 : 1);
                        pq.push({dist[l][dx][dy], dx, dy});
                    }    
                }
            }
        }
        int ret = INF;
        for(int i = 0; i <= h; i++){
            for(int j = 0; j <= w; j++){
                int val = 0;
                for(int t = 0; t < 3; t++){
                    val += dist[t][i][j];
                }
                if(MAP[i][j] == '#') val -= 2;
                ret = min(ret, val);
            }
        }
        cout << ret << "\n";       
    }
    return 0;
}