백준 1753번 https://www.acmicpc.net/problem/1753

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제

입력

1
2
3
4
5
6
7
8

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력

1
2
3
4
5

0
2
3
7
INF

최단 경로를 해결할 수 있는 알고리즘은 여러 가지가 있지만, 이 문제에서는 다익스트라 알고리즘을 이용하여 해결하겠습니다.

이 문제에서 시간 제한은 1초, 메모리 제한은 256 MB입니다.

정점의 최대 개수는 20,000이고, 간선의 최대 개수는 300,000입니다. 벨만 포드나 플로이드 와샬 알고리즘 경우에는 간선이나 정점의 수에 정비례하게 시간 복잡도가 증가합니다. 즉, |V| * |E| = 20,000 * 300,000 = 6,000,000,000입니다. 최악의 경우에 60억의 반복을 해야하므로 대략적으로 계산한다고 하더라고 1초 이내에 최단 경로를 탐색하는 것을 어려울 것입니다.

간선의 경로를 인접리스트로 구하게 된다면 최대 20,000 * 20,000 = 4억이고, int형임을 고려하면 더 큰 크기의 메모리를 필요하게 됩니다. 따라서 인접 리스트를 사용하는 것이 메모리적으로 효율적입니다.

하지만 저는 딕셔너리형과 섞에서 사용했습니다.

1

edges = [{} for _ in range(v)]

왜냐하면 문제에 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.와 같은 말이 있기 때문에 여러 개의 간선이 존재할 경우 제일 작은 값만 저장하기 위해서 입니다.

코드 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import sys
import heapq
INF = 200000000  # 문제에 나온 조건보다 큰 수

if __name__ == '__main__':
    v, e = map(int, sys.stdin.readline().split())
    k = int(sys.stdin.readline()) - 1
    vertexs = [INF] * v  # 각 정점까지 도착하는데 걸리는 경로
    vertexs[k] = 0

    edges = [{} for _ in range(v)] 
    for _ in range(e):
        a, b, c = map(int, sys.stdin.readline().split())
        if b-1 in edges[a - 1]:  # 여러 개의 간선이 존재할 경우 제일 작은 값만 저장
            edges[a - 1][b - 1] = min(edges[a - 1][b - 1], c)
        else:
            edges[a - 1][b - 1] = c

    hq = [(0, k)]  # 최소힙. [거리, 정점]
    while hq:
        distance, selected = heapq.heappop(hq) # 가장 가까운 거리에 있는 정점을 선택
        if distance > vertexs[selected]: continue
        for _v, _w in edges[selected].items():
            if vertexs[_v] > distance + _w:
                vertexs[_v] = distance + _w
                heapq.heappush(hq, (vertexs[_v], _v))

    print("\n".join(map(lambda x:"INF" if x == INF else str(x), vertexs)))