BOJ 9694 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 링크
(2023.04.03 기준 G3)

문제

M명의 정치인과 N개의 관계, 관계는 두 사람과 4단계로 나누어진 친밀도로 주어진다.
한신이는 0번, 최고의원은 M-1번일 때, 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화할 때의 최소화된 친밀도의 합과 만난 순서를 출력.

알고리즘

친밀도를 가중치로 하여금 최단 거리를 구하는 다익스트라를 돌리면 된다.

풀이

최단 거리는 구하기 쉽다. 하지만 다익스트라를 접한 지 얼마 되지 않았을 때에는, 만난 순서. 즉, 경로 추적이 힘들 수 있다.

다익스트라의 원리가 무엇인가? "x번 정점까지의 최단 거리 + x-y 가중치 < y번 정점까지의 최단거리"일 때마다 갱신을 한다. 생각해보면 경로도 단순하다. 거리가 갱신될 때마다 경로도 "x까지의 경로 + y"가 되는 것이다.

이런 그래프가 있다고 생각을 해보자. 1번부터 시작하여 다익스트라를 돌리면, 2번은 [1, [1, 2]], 3번은 [4, [1, 3]] 으로 갱신이 된다. (최단 거리, 경로)
하지만 2번에서 3번으로 다시 갱신이 되면 3번의 최단 거리는 3이 된다. 경로는? 2번 경로 + 3번 = [1, 2] + [3] = [1, 2, 3] 이 되는 것이다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef pair<int, vector<int>> piv;
const int INF = 1e9;

int N, M, x, y, z, d, dist[20];
vector<int> route[20];
vector<pi> graph[20];
priority_queue<pi, vector<pi>, greater<pi>> pq;

void solve(){
    cin >> N >> M;
    for (int i = 0; i < M; i++) graph[i].clear(), dist[i] = INF, route[i].clear(); // 초기화
    for (int i = 0; i < N; i++){ // 친밀도 그래프
        cin >> x >> y >> z; // 친밀도는 양방향
        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }

    pq.push({0, 0}); // 한신이는 0번
    dist[0] = 0, route[0] = {0}; // 최단 거리, 경로
    while (!pq.empty()){ // 다익스트라
        d = pq.top().first;
        x = pq.top().second;
        pq.pop();
        if (dist[x] < d) continue;
        for (auto yz: graph[x]){
            y = yz.first;
            z = yz.second;
            if (dist[y] > d + z){
                dist[y] = d + z;
                route[y].clear(); // 거리가 갱신될 때마다 경로도 같이 갱신
                for (int i = 0; i < route[x].size(); i++) route[y].push_back(route[x][i]);
                route[y].push_back(y);
                pq.push({dist[y], y});
            }
        }
    }

    if (dist[M - 1] < INF){ // 최고의원은 M-1번
        for (int i = 0; i < route[M - 1].size(); i++) cout << ' ' << route[M - 1][i];
        cout << '\n';
    }
    else cout << ' ' << -1 << '\n';
}

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

    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) cout << "Case #" << i << ":", solve();
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

for T in range(1, int(input()) + 1):
    print('Case #%d: ' % T, end = '')

    N, M = map(int, input().split())
    graph = [[] for _ in range(M)] # 친밀도 그래프
    for _ in range(N):
        x, y, z = map(int, input().split())
        graph[x].append((y, z)) # 친밀도는 양방향
        graph[y].append((x, z))

    queue = [(0, 0)] # 한신이는 0번
    distance = [[inf, []] for _ in range(M)] # 최단 거리, 경로
    distance[0] = [0, [0]]
    while queue: # 다익스트라
        d, x = heappop(queue)
        if distance[x][0] < d:
            continue
        for y, z in graph[x]:
            if distance[y][0] > d + z:
                distance[y] = [d + z, distance[x][1] + [y]] # 거리가 갱신될 때마다 경로도 같이 갱신
                heappush(queue, (distance[y][0], y))

    print(*distance[M - 1][1]) if distance[M - 1][0] < inf else print(-1) # 최고의원은 M-1번