[BOJ] 10217 : KCM Travel

문제 링크

10217번: KCM Travel (acmicpc.net)

10217번: KCM Travel

DP와 다익스트라 알고리즘을 함께 활용해야하는 문제였다.

풀이

처음에 Dp에 그 지점까지 왔을 때의 시간 또는 비용을 저장해서 다음 번에 다시 그 지점에 도착했을 때

시간적으로 혹은 비용적으로 더 비효율적이라면 멈추고 다른 경우를 생각하는 방식을 떠올렸다.

예전에 백트래킹 문제에서 이렇게 풀었던 기억이 나서 이번에도 백트래킹으로 접근했다.

하지만 백트래킹은 모든 경우를 다 탐색하다보니 시간초과가 났다. 어떻게든 시간을 줄여보려 했지만 안됐다.

그래서 다익스트라를 써야겠다고 생각. Dp를 어떻게 다익스트라에 접목시킬까?

사실 똑같다.

가장 짧은 소요시간을 출력해야 하므로 우선순위큐는 시간 기준 짧은 순으로 정렬.

만약 한 지점에 도달했을 때 같은 돈을 사용했다면 시간이 짧을 수록 좋은 경로이다.

즉 Dp[정점][비용] 대비 시간이 적을 수록 유리한 경로.

Dp[now][cost] < 현재까지 걸린시간 이라면 탐색을 멈추고 다음 경우로 간다.

 

<코드>

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
const int MAX_N = 100 + 5;
const int INF = INT_MAX;
typedef priority_queue <pair<pair<int,int>, int>, vector<pair<pair<int,int>, int>>, greater<pair<pair<int,int>,int>>> Priority_queue;
int T, N, M, K;
vector<pair<pair<int, int>, int>> Edge[MAX_N];
int Dp[MAX_N][10000 + 5];
 
void dijkstra(int st) {
    Priority_queue pq;
    pq.push({ { 0,st }, 0 });
    while (!pq.empty()) {
        int now = pq.top().first.second;
        int Time = pq.top().first.first;
        int cost = pq.top().second;
        pq.pop();
        if (Dp[now][cost] < Time)
            continue;
        Dp[now][cost] = Time;
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first.first;
            int acost = cost + Edge[now][i].first.second;
            int atime = Time + Edge[now][i].second;
            if (acost > M)
                continue;
            if (Dp[next][acost] <= atime)
                continue;
            for (int j = acost; j <= M; j++) {
                if (Dp[next][j] > atime)
                    Dp[next][j] = atime;
            }
            pq.push({ {atime, next},acost });
        }
    }
}
 
void Init() {
    for (int i = 0; i < MAX_N; i++) {
        Edge[i].clear();
    }
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < 10000 + 5; j++) {
            Dp[i][j] = INF;
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> N >> M >> K;
        Init();
        int ans = INF;
        for (int i = 0; i < K; i++) {
            int u, v, c, d;
            cin >> u >> v >> c >> d;
            Edge[u].push_back({ {v,c},d });
        }
        dijkstra(1);
        for (int i = 0; i <= M; i++) {
            ans = min(ans, Dp[N][i]);
        }
        if (ans == INF)
            cout << "Poor KCM\n";
        else cout << ans << "\n";
    }
    return 0;
}

마지막에 Dp[N]에 저장된 값중에 비용은 M이하면 얼마든 상관없으므로 가장 적게 걸린 시간을 출력하면 된다.