백준 1916 최소비용 구하기 / python

문제 :

풀이 point

다익스트라 알고리즘을 활용한다. heap을 활용한 알고리즘이다.
다익스트라 알고리즘은 이 곳을 참고한다.

다익스트라 알고리즘을 활용하면 아주 간단하게 목적지까지의 최단거리를 구할 수 있다.

간단히 설명하면 초기 거리를 모두 무한대로 설정한 후 가중치 간선들을 하나씩 집어넣어서 내가 기존에 알고 있는 길과 다음 노드로 가는 길의 비용을 비교하여 가장 적은 쪽을 선택한다.
이때 힙을 사용하기 때문에 효율적으로 비용이 가장 적은 노드들을 먼저 불러온다. 그렇기 때문에 이미 알고 잇는 길이 더 비용이 작다면 스킵한다. (이 때문에 가장 가중치가 적은 애들을 먼저 보는 최소힙이 필요하다)

풀이 코드

import sys
import heapq

input = sys.stdin.readline

INF = 10**18

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
dist = [INF]*(N+1)

for _ in range(M):
  a, b, c = map(int, input().split())
  graph[a].append([b, c])

start, end = map(int, input().split())

def dijkstra(s):
  pq = [] #리스트를 힙으로 쓰기 위해
  dist[s] = 0
  heapq.heappush(pq, (0, s))

  while pq:
    cost, node = heapq.heappop(pq) #힙에 남아있는 값중에서 비용 가장 작은

    if dist[node] < cost: #이미 알고 있는 길이 더 비용 작음
      continue

    for n, c in graph[node]: #다음 노드로 가는 길
      ncost = c+cost #다음 노드로 가는 비용

      if ncost < dist[n]: #다음 노드로 가는 현재 계산 비용이 알고 있는 다음 노드로 가는 비용보다 작다면
        dist[n] = ncost #갱신
        heapq.heappush(pq, (ncost, n))

dijkstra(start)
print(dist[end])