[Problem Solving] 백준 1916번 최소비용 구하기 문제풀이

백준 1916번 최소비용 구하기 문제 해설

1916번: 최소비용 구하기

모든 도시의 이동 비용이 양의 정수이고, 시작 지점에 대한 정보도 있으므로 해당 문제는 다익스트라 알고리즘을 활용하여 해결하면 된다.

 

다익스트라 알고리즘에 대한 설명은 다음을 참조하면 된다. 다익스트라 알고리즘 개념, 다익스트라 알고리즘 실습

 

다익스트라 알고리즘을 활용하여 코드를 작성하면 다음과 같다.

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
distance = [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(start):
  q = []
  heapq.heappush(q, (0,start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      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]))
 
Dijkstra(start)
 
print(distance[end])

 

해당 문제는 다익스트라 알고리즘을 구현할 수 있는지에 대해 물어보는 문제로 다익스트라 알고리즘을 구현하여 해결하였다.