[알고리즘] 다익스트라 알고리즘에서의 경로 복원, 백준 11779번: 최소비용 구하기 2 C++ 풀이까지

https://blog.encrypted.gg/1037

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.

---

플로이드 알고리즘에서는 경로 복원을 위해 nxt[u][v]에 u -> v로 갈 때 u 바로 다음에 방문할 곳을 저장했다. 

 

반면 다익스트라 알고리즘에서는 pre 테이블을 사용한다. 그리고 pre[u] 에는 시작점에서 u로 갈 때 u 직전에 방문해야 할 곳을 저장하면 된다.

 

두 알고리즘의 경로 복원 방식에 차이가 나는 이유가 뭘까? 이유는 알고리즘이 달라서일테고, 어떤 차이점때문에 플로이드 알고리즘에서는 nxt를 사용하고 다익스트라 알고리즘에서는 pre를 사용할까?

• start -> u1 -> u2 -> v 와 같은 경로를 생각해보자. 다익스트라 알고리즘을 따라가다보면 u2까지 확정될테고, u2 -> v가 우선순위 큐에서 가장 짧아서 u2 -> v 경로가 확정 될 것이다. 이렇게 된 경우 start -> v 에서 v 이전에 u2를 방문하는 것은 명확하며, 구현적으로도 간단하다.
  • 하지만 start -> v 에서 start 다음 u1, 그 다음 u2 이런 방식의 경로 저장은 정보 저장이 간단하지 않다. 추가적인 배열을 사용해서 역추적하며 따라가야 한다.
  • 즉, 다익스트라 알고리즘은 시작점에서 u1 u2 이런식으로 뻗어가며, 최종 v 까지의 경로를 확정하기에 pre를 사용하는 방식이 직관적이고 옳다.
• 그렇다면 플로이드는 어땠을까? 플로이드 알고리즘은 u -> v와 u -> k -> v를 비교한다. u -> k -> v가 더 짧은 경로일 경우 u 바로 다음에 방문할 노드로 업데이트 하는 것이 훨씬 직관적이다. 
  • 사실 플로이드에서 pre를 사용해 경로를 복원하는 방식은 엄청나게 비효율적이지는 않다.
  • 대신, 알고리즘의 흐름과 목적을 생각했을 때 pre를 사용하는 것은 자연스럽지 않은 것이다.
• 플로이드에서는 원래 경로 복원에 자연스러운 nxt를 사용하고, 다익스트라에서는 알고리즘의 특성상 pre를 사용하는 편이 더 직관적이고 효율적이라는 것으로 알아두자.

다시 경로 복원 알고리즘으로 돌아가자. pre[u]는 start -> u 에서 u 직전에 방문할 정점을 저장한다고 했다. 따라서 dist 테이블이 변경될 때 pre 테이블도 업데이트 하면 된다.

 

이렇게 1번 정점만 확정하고, 연결된 정점들을 우선순위 큐에 넣으면서 dist 테이블이 업데이트되고, pre[nxt]에는 cur을 넣게 된다. 

• cur : 현재 확정 중인 1번 노드이다.
• nxt : cur 노드와 연결된 노드이다.

 

바로 구현해보자.

https://www.acmicpc.net/problem/11779

 

/** 다익스트라 11779 최소비용 구하기 2 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int v, e, st, en;

vector<pair<int, int>> adj[1005];
const int INF = 0x3f3f3f3f;
int d[1005];   // 최단 거리 테이블
int pre[1005]; // 경로 복원 테이블

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> v >> e;
    fill(d, d + v + 1, INF);

    while (e--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 최소 힙

    cin >> st >> en;
    d[st] = 0;
    pq.push({d[st], st});

    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();

        // d[cur]과 우선순위 큐 정점이 다른 경우
        if (d[cur.second] != cur.first)
            continue;
        for (auto nxt : adj[cur.second])
        {
            if (d[nxt.second] <= d[cur.second] + nxt.first)
                continue;
            // cur을 거쳐 nxt로 가는게 더 가까운 경우
            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push({d[nxt.second], nxt.second});

            // d가 업데이트 될 때 pre 업데이트
            pre[nxt.second] = cur.second;
        }
    }

    cout << d[en] << '\n';

    deque<int> ans;
    int cur = en;
    while (cur != st)
    {
        ans.push_front(cur);
        cur = pre[cur];
    }
    ans.push_front(cur);

    cout << ans.size() << '\n';
    for (auto x : ans)
        cout << x << ' ';
}

 

최단 경로 테이블인 d가 업데이트 된다는 것은 현재 까지의 최단 경로 정보가 바뀐다는 것이고, 그 시점에서만 pre를 업데이트 해야 한다. 즉, d[cur]과 우선순위 큐에서 뽑은게 다른 경우 = 최단 경로가 아닌 경우에 업데이트하지 않게 조심해야 한다.