BOJ 1753 · 최단경로

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

한 개의 정점에서 다른 모든 정점으로 가는 최단 경로를 구해야 한다. 이 문제는 다익스트라 알고리즘을 이용하는 대표적인 문제다. 다익스트라 알고리즘을 활용하기 위해서 최소 힙(Min-heap)을 이용하면 편하다.

• C++은 STL에 있는 우선순위 큐(Priority Queue)를 이용하여 최소 힙을 사용하면 된다. 단, Priority Queue가 기본적으로 최대 힙(Max-heap)이므로, 비용(cost)에 -1을 곱해서 사용하거나, 연산자 오버로딩을 통해 순서를 바꿔서 사용하면 된다.
• Python은 Heapq를 이용하면 된다.
• 정점은 1~N이고, 인덱스는 0~N-1이다. 따라서, 입력받을 때 정점에 -1을 해주거나, 리스트를 N+1 길이로 선언하여 이용해야 한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct graph {
    int node, cost;
    bool operator < (const graph t) const { return cost > t.cost; }
};
 
int n, m, start;
const int INF = 1e9;
 
void dijkstra(vector<graph> a[], int dist[]) {
    priority_queue<graph> pq;
    pq.push({start, 0});
    dist[start] = 0;
    while (!pq.empty()) {
        int now = pq.top().node, cost = pq.top().cost;
        pq.pop();
        if (dist[now] < cost) continue;
        for (auto k : a[now]) {
            int next = k.node, ncost = k.cost+cost;
            if (dist[next] > ncost) {
                dist[next] = ncost;
                pq.push({next, ncost});
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    vector<graph> a[n];
    int dist[n];
    scanf("%d", &start); start--;
    for (int i=0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        a[u-1].push_back({v-1, w});
    }
    fill(dist, dist+n, INF);
    dijkstra(a, dist);
    for (auto i : dist) {
        if (i == INF) printf("INF\n");
        else printf("%d\n", i);
    }
    return 0;
}

✓ dist 배열을 INF로 초기화할 때, STL algorithm 라이브러리에 있는 fill 함수가 유용하다.

---

Python 3 소스코드

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

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

def dijkstra():
    pq = []
    heappush(pq, (0, start))
    dist[start] = 0
    while pq:
        cost, now = heappop(pq)
        if dist[now] < cost:
            continue
        for nxt, ncost in a[now]:
            ncost += cost
            if dist[nxt] > ncost:
                dist[nxt] = ncost
                heappush(pq, (ncost, nxt))

dijkstra()
for i in range(n):
    print("%d\n" % dist[i] if dist[i] != INF else "INF\n")

---

참고

• 백준 온라인 저지 : BOJ 1753
• 위키피디아 : 데이크스트라 알고리즘
• 위키피디아 : 힙 (자료 구조)