백준 10217 - KCM Travel(C++)

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

10217번: KCM Travel

Dp와 다익스트라 알고리즘을 합펴서 푸는 문제였습니다.

이동 비용이 M이하이면서, 최소시간을 구하는 문제입니다.

 

1에서 N까지 이동할 때, 최소 거리를 구하는 방법은 간단합니다.

하지만, N까지 이동할 수 있는 비용은 다를 수 있습니다.

따라서 2차원 배열을 이동해, X번 노드를 Y비용에 도착했을 경우로 만들어줘야 합니다.

 

저는 Distance[X][Y] = K라는 배열을 만들어, "X번 노드를 Y 비용으로 도착했을 때, K 비용이 들었다" 의 의미로 만들었습니다.

 

배열을 통해 기억하면서 풀기에 탐색 과정에서 비용의 조건만 추가하면 바로 맞을 수 있습니다.

 

여기서 코드 시간을 줄이는 방법을 생각해보겠습니다.

예를 들어, 7번 노드를 X비용으로 오는데 10초라는 시간이 걸렸다고 가정하겠습니다.

이때, X+1, X+2 비용일때는 10초보다 큰 시간이 걸렸습니다.

그렇다면, X+1. X+2 비용에서 탐색할 때는 각각의 시간으로 탐색하는 것이 좋을꺼 같습니까?

당연히 해당 경우도 10초라는 시간을 가지고 탐색하는 것이 효율적일 것입니다.

 

따라서 Y비용으로 X정점을 도착했을 때의 시간을 Y+1 ~ M까지의 비용과 비교해봅니다. 

비교하면서 자신보다 큰 시간이 있을 경우, 자신의 시간으로 바꿔줍니다. 

자신보다 작은 비용이 나올 때 까지만 반복하면 됩니다.

 

왜나하면, Y+K라는 비용일 때의 시간이 더 작다면 해당 비용 이후부터는 Y+K 비용일 때의 시간으로 바꿔서 이동하는 것이 효율적이기 때문입니다.

 

또한 이번에 탐색하려는 정점과 비용일때의 시간이 Distance에 저장된 값보다 크다면?

-> 전 탐색에서 더 효율적인 방법으로 바뀌었다는 의미입니다. 따라서 해당 경우에는 탐색할 필요가 없어집니다.

 

 

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

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

using namespace std;

int test_case;
int N, M, K;
vector<PP> connect[101]; // node, cost, time
int Distance[101][10001];

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

void Dijstra(){
    priority_queue<PP> q; // time, node, cost
    Distance[1][0] = 0;
    q.push({-0, {1,0}});
    while(!q.empty()){
        int x = q.top().S.F;
        int cost = q.top().S.S;
        int T = -q.top().F;
        q.pop();
        if(Distance[x][cost] < T) continue;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = connect[x][i].S.F + cost;
            int n_T = connect[x][i].S.S + T;
            if(n_cost <= M && n_T < Distance[xx][n_cost]){
                for(int j = n_cost + 1; j <= M; j++){ // 실행 시간 줄이기
                    if(Distance[xx][j] < n_T) break;
                    Distance[xx][j] = n_T;
                }
                Distance[xx][n_cost] = n_T;
                q.push({-Distance[xx][n_cost],{xx,n_cost}});
            }
        }
    }
}

void reset_connect(){
    for(int i = 1; i <= N; i++) connect[i].clear();
}

void solve(){
    reset_distance();
    Dijstra();
    reset_connect();
    int ans = INF;
    for(int i = 1; i <= M; i++){
        ans = min(ans, Distance[N][i]);
    }
    if(ans == INF) cout << "Poor KCM" << "\n";
    else cout << ans << "\n";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int i = 0; i < test_case; i++){
        cin >> N >> M >> K;
        for(int j = 1; j <= K; j++){
            int x, y, cost, t;
            cin >> x >> y >> cost >> t;
            connect[x].push_back({y,{cost,t}});
        }
        solve();
    }
    return 0;
}

 

 

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