우선순위 큐를 활용한 다익스트라 알고리즘 O(E log V)

일반적인 다익스트라 알고리즘의 경우 O(|V|^2 + |E|)이므로, 정점이나 간선의 수가 아주 많아지는 경우 시간 초과가 발생하여 문제를 풀 수 없는 경우가 있습니다.

 

그래서 여기서 개선된 방법이 바로 우선순위 큐(priority_queue)를 활용하여 다익스트라 알고리즘을 사용하는 방법입니다.

우선순위 큐를 활용하여 다익스트라 알고리즘을 사용하면, O(E log V) 시간에 최단경로를 찾을 수 있습니다.

 

그 이유는 기존 다익스트라 알고리즘의 경우 "특정 노드와 가장 거리가 짧은 노드"를 찾는 과정에서 매번 일일이 탐색하는 과정을 거쳐야 하는데, 우선순위 큐를 활용할 경우 top에서 그 값을 바로 빼올 수 있기 때문입니다.

물론 데이터를 힙에 저장하고 갱신하는 과정에서 log 시간이 걸리긴 하지만, 결과적으로는 훨씬 짧은 시간에 알고리즘을 수행할 수 있게 됩니다.

 

이를 구체적인 예시로 확인해보기 위해, 백준 Online Judge의 1504번 : '특정한 최단 경로' 문제를 풀이해보도록 하겠습니다.

 

 

BOJ 1504 특정한 최단 경로

 

E개의 간선들이 주어질 때, 1번 정점 → A번 정점 → B번 정점 → N번 정점으로 가는 경로와, 1번 정점 → B번 정점 → A번 정점 → N번 정점으로 가는 경로 중 최단 경로의 길이를 출력하는 문제입니다.

 

우선순위 큐를 활용한 다익스트라 알고리즘을 구현하여 문제를 풀이해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
#define MAX 805
using namespace std;

int N, E;
vector<pair<int, int>> adj[MAX];
int dist[MAX];

void Dijkstra(int start) {
    for(int i=1; i<=N; i++) dist[i] = INT_MAX;
    dist[start] = 0;

    priority_queue<pair<int, int>> pQueue;
    pQueue.push({0, start});

    while(!pQueue.empty()) {
        int dist1 = -pQueue.top().first;
        int curr = pQueue.top().second;

        pQueue.pop();

        for(int i=0; i<adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int dist2 = adj[curr][i].second;

            if(dist1 + dist2 < dist[next]) {
                dist[next] = dist1 + dist2;
                pQueue.push({-dist[next], next});
            }
        }
    }
}

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

    cin >> N >> E;

    for(int i=0; i<E; i++) {
        int a, b, c; cin >> a >> b >> c;

        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    int A, B; cin >> A >> B;

    int route1 = 0, route2 = 0;
    bool check1 = true, check2 = true;

    Dijkstra(1);
    if(dist[A] == INT_MAX) check1 = false;
    else route1 += dist[A];

    Dijkstra(A);
    if(dist[B] == INT_MAX) check1 = false;
    else route1 += dist[B];

    Dijkstra(B);
    if(dist[N] == INT_MAX) check1 = false;
    else route1 += dist[N];


    Dijkstra(1);
    if(dist[B] == INT_MAX) check2 = false;
    else route2 += dist[B];

    Dijkstra(B);
    if(dist[A] == INT_MAX) check2 = false;
    else route2 += dist[A];

    Dijkstra(A);
    if(dist[N] == INT_MAX) check2 = false;
    else route2 += dist[N];

    if(!check1 && !check2) cout << "-1";
    else if(!check1) cout << route2;
    else if(!check2) cout << route1;
    else cout << min(route1, route2);
}

 

이 문제의 경우 다익스트라 알고리즘을 여러 번 사용해야 합니다.

 

먼저 1번 정점에서 다익스트라를 사용한 뒤 A번 정점까지의 최단 거리와 B번 정점까지의 최단 거리를 구합니다.

그 다음 A번 정점에서 다익스트라를 사용하여 B번 정점까지의 최단 거리와 N번 정점까지의 최단 거리를 구해야합니다.

B번 정점에서도 마찬가지로 A번 정점까지의 거리와 N번 정점까지의 거리를 구해야합니다. (간선의 방향이 있으므로 B에서 A로 거리는 다를 수 있습니다.)

 

이제 위에서 구한 거리들을 합쳐서 두 경로 중 최단 경로의 길이를 구해주면 됩니다.

이 때 위의 경로들 중에서 INF로 초기화한 값들 중 갱신되지 않은 것이 있을 수 있는데 이것은 경로가 존재하지 않는 경우에 해당하므로, bool 변수를 적당히 활용하여 -1을 출력해줄 수 있도록 해주면 됩니다.

 

제출해보면 정답 처리를 받을 수 있습니다.