다익스트라 알고리즘 + DP를 접목하여 풀이하는 문제 (백준 BOJ 10217)

다익스트라 알고리즘과 DP를 접목하여 풀이하는 문제를 다루어보도록 하겠습니다.

대표적인 예시를 들기 위해 백준 BOJ의 10217번 문제 'KCM Travel'을 예시로 풀이하겠습니다.

 

M원 이하로 비용을 사용하여 1번 노드에서 N번 노드까지 가는데 드는 최소 시간을 구하는 문제입니다.

(변수들의 입력 순서나 변수 입력 범위는 백준 BOJ 10217번 문제를 직접 참고하기 바랍니다.)

 

 

 

이 문제에서는 정해진 비용 이내로 갈 수 있는 지점이 제한되어 있다는 조건이 추가되어 있습니다.

따라서 특정 노드까지 이동했을 때의 비용을 저장할 수 있는 배열이 추가로 필요합니다.

그렇기 때문에 dist라는 배열을 따로 선언하여 dp로 문제를 해결해주어야 합니다.

 

dp 문제의 경우에는 배열을 어떻게 정의하느냐에 따라서 풀이의 간결성이 결정됩니다.

가장 대표적인 방법은 dist[i][j]를 i번 노드까지 j의 비용을 사용하여 이동할 수 있는 최단 거리라고 정의하는 것입니다.

(위의 그림을 참고하시면 됩니다.)

 

이제 우선순위 큐를 이용한 다익스트라 알고리즘을 사용하여 문제를 풀이해주면 됩니다.

다만 이 문제의 경우 그럼에도 불구하고 시간 초과가 발생할 수 있는데, 이를 피하기 위해 계산의 소모를 줄여주어야 합니다.

 

두 가지 방법으로 TLE를 피할 수 있습니다.

첫 번째는 거리 갱신이 안되는 경우 즉 아래 코드에서 tdist >= dist[curr][cost]인 경우 continue 해주어 계산 낭비를 줄이는 것이고, 두 번째는 비용이 제한 값 M을 넘어가는 경우 continue로 skip해주는 것입니다.

 

 

#include <bits/stdc++.h>
#define MAX_V 105
#define MAX_M 10005
using namespace std;

struct edge { int dest, cost, tdist; };
vector<edge> adj[MAX_M];
int dist[MAX_V][MAX_M] = {}; // dist[i][j] : shortest distance to node "i" using cost "j"

struct compare {
    bool operator()(edge &a, edge &b) {
        return a.cost > b.cost;
    }
};

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

    int T; cin >> T;

    while(T--) {
        for(int i=0; i<MAX_M; i++) adj[i].clear();
        for(int i=0; i<MAX_V; i++)
            for(int j=0; j<MAX_M; j++) dist[i][j] = INT_MAX;

        int N, M, K; cin >> N >> M >> K;

        for(int i=0; i<K; i++) {
            int u, v, c, d; cin >> u >> v >> c >> d;
            adj[u].push_back({v, c, d});
        }

        priority_queue<edge, vector<edge>, compare> pQueue;
        pQueue.push({1, 0, 0}); dist[1][0] = 0;

        while(!pQueue.empty()) {
            int curr = pQueue.top().dest;
            int cost = pQueue.top().cost;
            int tdist = pQueue.top().tdist;

            pQueue.pop();

            if(tdist > dist[curr][cost] || cost > M) continue;

            for(int i=0; i<adj[curr].size(); i++) {
                int next = adj[curr][i].dest;
                int cost_ = adj[curr][i].cost + cost;
                int tdist_ = adj[curr][i].tdist + tdist;

                if(tdist_ >= dist[next][cost_] || cost_ > M) continue;

                dist[next][cost_] = tdist_;
                pQueue.push({next, cost_, tdist_});
            }
        }

        int ans = INT_MAX;
        for(int i=1; i<=M; i++) ans = min(ans, dist[N][i]);

        if(ans != INT_MAX) cout << ans << "\n";
        else cout << "Poor KCM\n";
    }
}

 

풀이 코드는 위와 같습니다.

pair를 여러 번 사용하는 것보다 위와 같이 struct를 사용하는 것이 코드 작동 시간을 조금 더 줄일 수 있기 때문에 사용하는 편이 낫다고 합니다.

(실제로 저도 struct를 사용하여 제한 시간 10초 중 거의 9초 후반대로 테스트케이스를 통과하였습니다.)