최단경로

백준 1753

우선순위 큐를 이용한 다익스트라 알고리즘

import sys
import heapq


V, E = map(int, sys.stdin.readline().split())
s = int(sys.stdin.readline())

graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    #첫번째 원소를 기준으로 우선순위를 설정하므로 w가 우선순위 값이 되도록 w먼저
    graph[u].append((w,v))

inf = sys.maxsize
dp = [inf]*(V+1)

heap = []
def dk(s):
    #시작노드로 가기 위한 최단경로는 0으로 설정하여 큐에 삽입
    dp[s] = 0
    heapq.heappush(heap,(0, s))

    while heap:
        nw, nn = heapq.heappop(heap)
        #현재 dp와 비교하여 가중치가 더 큰 튜플이면 무시
        #이미 now_node에 now_w보다 더 짧은 길이로 방문한 적이 있다면
        if dp[nn] < nw:
            continue
        #현재 노드와 연결된 다른 인접노드 확인
        for ad_w, ad_n in graph[nn]:
            #현재 정점까지의 가중치+현재에서 다음 정점까지의 가중치
            if nw+ad_w < dp[ad_n]: #현재 노드를 거치는게 더 짧은 경우
                dp[ad_n] = nw+ad_w
                heapq.heappush(heap, (nw+ad_w, ad_n))

dk(s)
for ele in dp[1:]:
    if ele==inf:
        print("INF")
    else:
        print(ele)

첫 번째 원소를 기준으로 우선순위를 설정하므로 w가 우선순위 값이 되도록 w먼저 넣는다.

힙이 비어 있지 않을 동안 힙에서 가중치와 정점을 pop해서
현재 점의 dp값이 가중치보다 작은 경우 더 짧은 거리로 그 정점을 방문했다는 뜻이므로 무시한다.

현재 정점과 연결된 정점들을 확인하며 인접 노드로의 거리를 구할건데, 현재 정점까지의 가중치와 현재 정점에서 인접 정점까지의 가중치를 더한 값이 인접 노드의 dp값 보다 작다면 현재 노드를 거치는 것이 더 빠르다는 뜻이므로 갱신해주고 힙에 넣어준다.

후하 어렵다ㅜㅜ 내일 다시 풀어봐야지..

참고
참고2