[백준/Python] 1916번: 최소비용 구하기

문제

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

1916번: 최소비용 구하기

---

문제 요약

N개의 도시(정점)와 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스(간선)가 있다.

+ 각 도시들은 번호가 존재하고, 버스마다 비용(양수)이 존재한다.

 

출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

---

코드

from collections import deque
import sys
import heapq
input = sys.stdin.readline

def dijstra(start):
    que = []
    heapq.heappush(que, (0, start))
    costs[start] = 0    

    while que:
        dist, num = heapq.heappop(que)
        
        # 최소힙 때문에 push된 최소 비용이 바로 pop되지 않는다. 
        # push와 pop 중간에 더 적은 비용(costs)이 갱신되어 있을 수 있다.
        if costs[num] < dist:
            continue
        
        for i in graph[num]: #i[0]: num애 인접한 도시, i[1]: num에서 i[0]까지 비용
            cost = dist + i[1]
            if cost < costs[i[0]]:
                costs[i[0]] = cost
                heapq.heappush(que, (cost, i[0]))

n = int(input()) # 도시 개수 (정점)
m = int(input()) # 버스 개수 (간선)

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

INF = int(1e9)

costs = [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())

dijstra(start)

print(costs[end])

---

코드 설명

다익스트라 알고리즘을 이용해 문제를 해결한다.

 

< 다익스트라 알고리즘 >

1. 시작점으로부터 현재까지 발견된 각 정점까지 최소 비용을 저장하는 배열을 생성한다.

+ 시작점: 0, 나머지: 무한

2. 우선순위 큐(최소 힙)을 사용하여 방문하지 않은 정점 중 최소 비용이 가장 작은 정점을 선택한다.

+ 시작점부터 선택한다.

3. 선택한 정점과 인접한 정점들의 최단 거리를 갱신한다.

+ 이전까지 발견된 최소 비용과 선택된 정점을 통해 이동하는 비용을 비교하여 갱신한다.

4. 갱신한 정점을 우선순위 큐에 삽입합한다.

 

5. 위 과정을 모든 우선순위 큐가 비어있을 때까지 반복한다.