BOJ 1238 · 파티

알고리즘 분류 : 다익스트라  

각 학생이 각자 자신의 마을에서 출발하고, X 마을에서 파티를 하고, 다시 자신의 마을로 돌아오는 시간을 맞추는 문제다. 마을 간의 이동은 1 이상의 소요 시간이 걸리므로, 다익스트라 알고리즘을 이용해야 한다.

• 이 문제는 다익스트라 알고리즘을 두 번만 호출해서 해결할 수 있다.
• 출발의 기준을 i (1<=i<=N)로 두는 것이 아니라, 출발을 X로 둬서, X → i 와 X ← i 라고 생각한다.
• 위 방법을 사용하기 위해서 인접 리스트를 2개 선언하여, 원래 방향과 반대 방향을 저장한다.
• 각 인접 리스트에 대해 다익스트라 알고리즘을 돌리고, 이동 거리를 dist 배열에 저장한다.
• 정답은 dist[i][0] + dist[i][1] 중에서, 가장 큰 값이다.

---

C++ 소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct town {
    int road, cost;
    bool operator < (const town t) const { return cost > t.cost; }
};

int n, m, x;
const int INF = 1e9;

void dijkstra(vector<town> v[], int dist[][2], int direct) {
    priority_queue<town> pq;
    pq.push({x-1, 0});
    dist[x-1][direct] = 0;
    while (!pq.empty()) {
        int now = pq.top().road, cost = pq.top().cost;
        pq.pop();
        if (dist[now][direct] < cost) continue;
        for (auto k : v[now]) {
            int next = k.road, ncost = cost+k.cost;
            if (dist[next][direct] > ncost) {
                dist[next][direct] = ncost;
                pq.push({next, ncost});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m >> x;
    vector<town> a[n], b[n];
    int dist[n][2];
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u-1].push_back({v-1, w});
        b[v-1].push_back({u-1, w});
    }
    fill(&dist[0][0], &dist[n][0], INF);
    dijkstra(a, dist, 0);
    dijkstra(b, dist, 1);
    int ans = 0;
    for (int i=0; i<n; i++) {
        int temp = dist[i][0] + dist[i][1];
        if (ans < temp) ans = temp;
    }
    cout << ans << '\n';
    return 0;
}

✓ fill 함수는 보통 1차원 배열(또는 벡터)을 초기화할 때 이용하지만, 배열의 주소를 이용하면 2차원 배열도 초기화할 수 있다.

---

Python 3 소스코드

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

INF = 1e9
n, m, x = map(int, input().split())
dist = [[INF]*2 for _ in range(n)]
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(m):
    u, v, w = map(int, input().split())
    a[u-1].append([v-1, w])
    b[v-1].append([u-1, w])

def dijkstra(k, direct):
    pq = []
    heappush(pq, (0, x-1))
    dist[x-1][direct] = 0
    while pq:
        cost, now = heappop(pq)
        if dist[now][direct] < cost:
            continue
        for nxt, ncost in k[now]:
            ncost += cost
            if dist[nxt][direct] > ncost:
                dist[nxt][direct] = ncost
                heappush(pq, (ncost, nxt))

dijkstra(a, 0)
dijkstra(b, 1)
ans = 0
for i in range(n):
    ans = max(ans, sum(dist[i]))
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 1238
• 최단경로
• 위키피디아 : 데이크스트라 알고리즘