(Python) - BOJ(1916번) : 최소비용 구하기

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

1916번: 최소비용 구하기

---

• 문제 : 

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

 

 

---

• 풀이 :

다익스트라 알고리즘을 구현할 수 있는가에 대한 문제이다. 

분명히 이론상으로도 알고 흐름도 알고있었는데 구현하려니까 잔실수가 많이 나왔다.

 

다익스트라 알고리즘이란 가중치가 있는 방향 그래프에서 한 노드로부터 다른 모든 노드에 도달하는 최소비용을 찾는 알고리즘이다.

알고리즘의 흐름은 다음과 같다.

1. 시작할 노드를 정하고 다른 모든 노드까지의 거리를 무한대값으로 초기화.

2. 시작노드의 거리는 0으로 셋팅하고 가장 거리가 짧은 노드부터 연결된 간선을 모두 탐색한다.

3. 이 때, 시작노드에서 탐색중인 노드까지의 최소비용보다 다른 노드를 통해서 가는 최소비용이 더 작은 경우만 비교한다.

4. 간선들을 탐색하며 현재 노드를 경유하여 다음 노드로 진행하는 것의 비용이 그렇지 않은 비용보다 작을 때만 heap에 넣고 탐색을 진행한다. 

 

 

---

• 소스코드 : 

import sys
import heapq as hq
input = sys.stdin.readline


if __name__ == "__main__":
    N = int(input())
    M = int(input())
    bus = [[] for _ in range(N+1)]
    for _ in range(M):
        start,end,cost = map(int,input().split())
        bus[start].append([end,cost])
    start,end = map(int,input().split())
    heap = [[0,start]]
    distance = [100000001 for _ in range(N+1)]
    distance[start] = 0
    while heap:
        dis,now = hq.heappop(heap)
        if distance[now] < dis:
            continue
        for i in bus[now]:
            cost = dis + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                hq.heappush(heap, (cost, i[0]))
    print(distance[end])