[백준] 1916번 최소비용 구하기 - 파이썬

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

1916번: 최소비용 구하기

import sys
import heapq

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
INF = int(1e9)
distance = [INF] * (n+1)

graph = [[] for i in range(n+1)]

for _ in range(m):
    a,b, cost = map(int,sys.stdin.readline().split())
    graph[a].append((b,cost))

start,end = map(int,sys.stdin.readline().split())

def dihkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance[start]=0
    while q:
        dist, now =heapq.heappop(q)

        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

dihkstra(start)

print(distance[end])

이 문제는 다익스트라이다.

가장 기본적인 다익스트라이니 까먹지말자!

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신하는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 '더 짧은 경로도 있었네? 이제부터는 이경로가 제일 짧은 경로야'라고 판단하는 것이다. 따라서 '방문하지 않은 노드중에서 현재 최단 거리가 가장 짧은 노드를 확인' 하는 것이다.