[WEEK03] 백준 1916 최소비용 구하기

문제

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

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

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

풀이

특정노드에서 특정노드까지 가는 최소비용 계산으로 다익스트라 알고리즘을 사용하면 된다.

우선 정점 개수만큼의 리스트를 선언하고 무한대로 초기화 해준다. 이 리스트는 시작 노드부터 다른 노드까지의 최소 비용을 저장해주는데 사용할 것이다.

시작노드에서 시작노드까지 가는 비용은 0이므로 0으로 초기화를 해준 뒤, 최소힙에 넣어준다. 이제부터 최소비용 리스트에서 값이 가장 노드를 선택하여 다음 노드까지의 거리에 더하면서 다음 노드의 최소비용을 더 작은 값으로 갱신할 것이다.

즉, 이 과정을 반복하면 된다. 최소비용 테이블에서 가장 작은 값을 가지는 노드를 선택해 연결되어있는 노드까지의 비용을 (현재 노드까지 비용 + 현재 노드에서 다음 노드까지의 비용), (현재 저장되어있는 다음 노드까지의 비용) 두개의 값을 비교해서 더 작은 값으로 갱신해주면 된다.

전체코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        # end_city 노드가 뽑히면 현재노드까지는 최단거리 완료된거임
        if now == end_city:
            print(dist)
            return
        # 방문 처리 끝나고 나서 우선순위 밀려나서 남아있는것들 처리
        if distance[now] < dist:
            continue

        # 현재 노드까지의 거리에 다음 노드 까지의 거리를 더한것을
        for i in graph[now]:
            cost = dist + i[1]
            # 비교하여 더 작으면 갱신
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [sys.maxsize] * (n + 1)

for _ in range(m):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))

start_city, end_city = map(int, input().split())
dijkstra(start_city)

반복하다가 힙에서 도착노드의 값이 나오면 도착노드 까지의 최소비용을 출력하고 종료하면 된다.