[백준] 1916 파이썬(python) : 최소비용 구하기 - 다익스트라

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

1916번: 최소비용 구하기

 

 

import heapq
import sys
n = int(input())
m = int(input())
INF = int(1e9) #1
graph = [ [] for _ in range(n+1) ]
visit = [INF] *(n+1)

for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((c, b)) #2
start, end = map(int, sys.stdin.readline().split())

def djikstra(x):
    q = []
    heapq.heappush(q, (0, x)) #3
    visit[x] = 0 #4
    while q:
        cost, x = heapq.heappop(q) #5
        if visit[x] < cost: #6
            continue
        for new_cost, new_node in graph[x]: #7
            nc = cost + new_cost #8
            if visit[new_node] > nc: #9
                heapq.heappush(q, (nc, new_node)) #10
                visit[new_node] = nc

djikstra(start)
print(visit[end])

 

#1 : 무한에 가까운 값

#2 : (c, b) 순서로 넣는 이유는 최소힙을 이용해야 하는데 최소힙은 튜플의 첫번째 원소를 기준으로 정렬하기 때문이다.

#3 : 시작노드의 값은 0이고 시작 노드 x를 q에 넣는다.

#4 : 시작노드의 값 0으로 설정

#5 : 노드까지의 거리(cost)와 노드

#6 : 다익스트라는 최소값 갱신을 위한 알고리즘이므로 기존값이 더 작다면 반복문을 넘어간다. 이 코드가 없으면 시간초과가 발생한다.

#7 : 현재노드에 연결되어 있는 새로운 노드까지의 거리, 새로운 노드

#8 : nc는 시작노드에서부터 새로운 노드까지의 최소거리

#9 : 기존에 있던 거리보다 최소값에 새로운노드로 가는 거리 추가한 값이 더 작으면

#10 : 최소힙에 새로운 노드까지의 최소거리와 새로운 노드를 추가

 

 

그래프 이론 문제에서 늘 쓰던 visit리스트지만 이렇게 활용할 수 있다는것을 배울 수 있었다. 다익스트라 알고리즘은 이론으로 들을때는 이해하기 쉬웠는데 코드로 짜보려니까 어려운것 같다. 복기가 필요하다.