[Python/파이썬] 백준 알고리즘 1753번 - 최단경로 (다익스트라/Dijkstra)

 

 

 

<풀이>

"""
1. 아이디어
- 한점 시작, 모든 거리 : 다익스트라
- 간선, 인접리스트 저장
- 거리배열 무한대 초기화
- 시작점 : 거리배열 0, heap에 넣어주기
- 힙에서 빼면서 다음의 것들 수행
    - 최신값인지 먼저 확인
    - 간선을 타고 간 비용이 더 작으면 갱신

2. 시간복잡도
- 다익스트라 : O(ElgV)
    - E : 3e5   (문제에서 1 <= E <= 300,000 이므로)
    - V : 2e4, lgV ~= 20    (1 <= V <= 200,000)
    - ElgV = 6e6    -> 가능

3. 변수
- 힙 : (비용, 노드번호)
- 거리 배열 : 비용 int[]
- 간선을 저장하는 인접리스트 : (비용, 노드번호)[]
"""
import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

V, E = map(int, input().split())
K = int(input())
edge = [[] for _ in range(V + 1)]
dist = [INF for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    edge[u].append([w, v])

dist[K] = 0
heap = [[0, K]]
while heap:
    ew, ev = heapq.heappop(heap)
    if dist[ev] != ew: continue
    for nw, nv in edge[ev]:
        if dist[nv] > ew + nw:
            dist[nv] = ew + nw
            heapq.heappush(heap, [dist[nv], nv])


for i in range(1, V + 1):
    if dist[i] == INF: print("INF")
    else: print(dist[i])

edge는 각각의 노드들의 인접 리스트이다. 즉 예를들어 edge[1]은 1번 노드와 연결된 인접 노드들의 정보들이 담겨 있다. [[2, 2], [4, 3]]과 같은 형식으로. ([[가중치, 타겟노드]]이다. 따라서 2번 노드, 3번 노드로 갈 수 있고 2번 노드에 연결된 간선의 가중치는 2이고 3번 노드에 연결된 간선의 가중치는 4라는 의미이다.)

dist는 각 노드들까지 도달하는데 필요한 최소 가중치 값이 담기는 리스트이다.

시작 노드를 1번노드라고 하면 dist[3]은 1번 노드에서 3번 노드까지 갈 때 필요한 최소 가중치 값이다.

(시작 노드의 최소 가중치 값은 0으로 한다. 따라서 dist[1] 값은 0이다.)

while문으로 heap을 pop하고 for문을 돌려 push하는 꼴은 BFS에서 queue를 사용하는 꼴과 흡사하다.

 

 

 

<핵심 정리>

1. 다익스트라는 힙과 while문을 이용해 구현한다.

2. 다익스트라는 최소 간선 가중치 값을 구하기 위한 알고리즘이다. (최단 경로 찾기 알고리즘)

3. 다익스트라는 "한 점"에서 여러 다른 점으로 갈 때 구하는 알고리즘이다.