백준 9376 - 탈옥(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9376

9376번: 탈옥

다익스트라를 사용한 문제입니다. 

문제를 풀기위해 새로운 접근이 필요했습니다.

상근이가 두 죄수를 탈옥하기 위해 열어야하는 최수 문 갯수를 구하는 문제입니다.

 

실수할 수 있는 부분이 있어, 많이 틀렸던 문제입니다.

문제에서 문을 열 수 있는 사람은 상근이와 두 죄수입니다.

 

그렇다면 생각할 수 있는 경우는 3가지입니다.

1. 상근이만 문을 열어 죄수들을 데려갈 경우

2. 죄수1이 죄수2를 데리고 나갈 경우

3. 죄수2가 죄수1을 데리고 나갈 경우

 

탐색 중, 3명이 동시에 만나는 지점이 탈출할 수 있는 최소점이 될 가능성이 있는 지점입니다.

해당 지점들을 찾아서 값을 계속 비교해주면 됩니다.

 

3경우를 모두 다익스트라를 통해 최소로 문을 열고 나갈 때의 값을 찾습니다.

3경우를 모두 더해, (X, Y) 좌표에서의 값을 찾습니다.

여기서, 어떤 좌표가 문일 경우, 1번만 열어도 되지만, 3명이 모두 열었다고 되어있습니다. 따라서, -2를 해줘야합니다.

 

이 좌표들을 모두 비교해, 가장 작은 값을 가져오면 됐습니다.

 

어려운 문제였습니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define PP pair<int, P>
#define F first
#define S second
#define INF 987654321

using namespace std;

int test_case;
int N, M;
char map[105][105];
int Distance[3][105][105];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<P> start;

void reset_distance(){
    for(int k = 0; k < 3; k++){
        for(int i = 0; i <= N+1; i++){
            for(int j = 0; j <= M+1; j++){
                Distance[k][i][j] = INF;
            }
        }
    }
}

void Dijstra(P X, int cnt){
    priority_queue<PP> q;
    q.push({-0, X});
    Distance[cnt][X.F][X.S] = 0;
    while(!q.empty()){
        int x = q.top().S.F;
        int y = q.top().S.S;
        int cost = -q.top().F;
        q.pop();
        if(Distance[cnt][x][y] < cost) continue;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 0 && xx <= N+1 && yy >= 0 && yy <= M+1){
                if(map[xx][yy] == '*') continue;
                if(map[xx][yy] == '#'){
                    if(Distance[cnt][xx][yy] > cost + 1){
                        Distance[cnt][xx][yy] = cost + 1;
                        q.push({-(cost + 1), {xx, yy}});
                    }
                }
                else if(map[xx][yy] == '.' || map[xx][yy] == '$'){
                    if(Distance[cnt][xx][yy] > cost){
                        Distance[cnt][xx][yy] = cost;
                        q.push({-cost, {xx, yy}});
                    }
                }
            }
        }
    }
}

void solve(){
    long long int ans = INF;
    reset_distance();
    for(int i = 0; i < 3; i++){
        Dijstra(start[i], i);
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == '*') continue;
            long long int sum = Distance[0][i][j] + Distance[1][i][j] + Distance[2][i][j];
            if(map[i][j] == '#') sum -= 2;
            if(sum >= 0) ans = min(ans, sum);
        }
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int k = 1; k <= test_case; k++){
        start.clear();
        cin >> N >> M;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                cin >> map[i][j];
                if(map[i][j] == '$'){
                    start.push_back({i,j});
                }
            }
        }
        for(int i = 0; i <= N+1; i++){
            map[i][0] = '.';
            map[i][M+1] = '.';
        } 
        for(int i = 0; i <= M+1; i++){
            map[0][i] = '.';
            map[N+1][i] = '.';
        } 
        start.push_back({0, 0});
        solve();
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요