#289 백준 파이썬 [1766] 최단경로 - 다익스트라

https://www.acmicpc.net/problem/1753

 

SOLUTION

해당 문제는 다익스트라 알고리즘으로 풀 수 있다.

다익스트라 알고리즘은 https://www.youtube.com/watch?v=611B-9zk2o4이 분이 굉장히 잘 설명해주셨다.

 

 

서로서로 연결된 그래프의

K번째 노드에서 1,2,3, ... V개의 노드에 도달하는 가장 짧은 거리들을 구하는 것이다.

이 때 가장 짧은 노드는 지속적으로 갱신되기 때문에 우선 순위 큐를 구현하여 처리해야한다. 일반 리스트에 append하고 최소값을 구하는 방법으로는 시간 복잡도가 굉장히 오래걸리기 때문.

우선 순위 큐는 힙으로 구현할 수 있다. 힙에 추가 및 삭제되며 저장될 때는 이진 트리를 따르기 때문에 빠르게 최소값을 출력할 수 있다.

 

다음과 같은 알고리즘을 따른다.

1) 큐에 [0, K]를 저장한다. [거리, 노드]

2) 큐에서 가장 거리가 적은 리스트를 pop한다. (=mid)

3) 현재 연결된 가장 짧은 노드에 연결된 다른 노드 (=end)를 전부 탐색하여 K에서 end 바로 가는 과거 최소값과 현재 mid를 거쳐 end로 가는 것 중 더 짧은 것을 K_distance[end]에 입력한다.

4) 우선 순위 큐에 [갱신된 end까지의 거리, end노드] 를 추가해준다.

5) 현재 연결된 가장 짧은 노드부터 탐색하여 노드를 전부 탐색 할 때 까지 2,3,4를 반복한다.

 

PYTHON CODE

import heapq
import sys

#입력
V, E = map(int, input().split())
K = int(input())
INF = 10 * V + 1 #최댓값 설정
distance = [[] for _ in range(V+1)] # V*V배열로 만들면 메모리가 초과된다

for _ in range(E):
    start, end, dist = map(int, sys.stdin.readline().split())
    distance[start].append([end, dist]) #시작 리스트에 도착지와 거리를 입력
    
    
#다익스트라 알고리즘
queue = [] #우선순위 큐 -> 힙으로 구현해줌
K_distance = [INF for _ in range(V+1)] #답이 될 K로부터의 거리
K_distance[K] = 0 #자기 자신은 0
heapq.heappush(queue, [0, K]) #자기 자신으로부터 우선순위 큐를 시작한다

while queue:
    mid = heapq.heappop(queue) #현재 가장 가까운 거리의 노드를 pop [거리, 노드 위치]
    for end in distance[mid[1]]: #가장 가까운 노드에 연결된 모든 노드들 end에 대하여
        if K_distance[end[0]] > mid[0] + end[1]: #mid노드를 거치는 게 end로 바로 가는 것보다 효율적이라면
            K_distance[end[0]] = mid[0] + end[1] #해당 거리를 저장
            heapq.heappush(queue, [K_distance[end[0]], end[0]]) #큐에 [갱신된 거리, 노드 위치] 삽입

#출력
for i in range(1, V+1):
    if K_distance[i] == INF:
        print("INF")
    else:
        print(K_distance[i])