[Python] 백준 1916번 문제, 최소 비용 구하기

<문제 링크>

 

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

1916번: 최소비용 구하기

 

---

<풀이>

 

우선순위 큐를 사용한 다익스트라를 사용하면 문제를 쉽게 해결할 수 있다.

모든 상황을 고려하는 것보다 우선순위 큐를 사용해 최소 비용들을 갱신하면 속도를 올릴 수 있다.

 

가중치가 작은 순서대로 정렬되어 있는 우선순위 큐에서 하나씩 꺼내 distance와 city에 값을 넣는다.

그런 다음 cost[city]가 초기화 되어 -1이 아니거나 이미 갱신이 됐지만 distance보다 작은 값을 가지고 있을 경우, 갱신할 필요가 없기 때문에 continue를 통해 다음 큐 값을 꺼낸다.

그렇다면 갱신이 필요한 경우, city에서 갈 수 있는 다른 city인 C가 있다면 C로 가는 값은 distance + city에서 C로 가는 값 weight이다.

그래서 cost[C]가 -1이거나 weight 값보다 큰 경우에 weight로 갱신시켜주며, que에 넣어준다.

 

이 과정을 반복해 갱신된 값들을 우선순위 큐에 넣어 큐가 비어질 때까지 갱신 작업을 진행한다.

 

---

<코드>

city_count: 시티 갯수

bus_count: 버스 갯수

cost: 시티 별 최소 비용을 담는 리스트

que: 우선순위 큐

city: 현재 포커싱 시티

distance: 현재 city에 오는 거리

---

import sys
import heapq

# 다익스트라 알고리즘
def dijkstra(start):
    que = [] # 우선순위 큐
    # init
    heapq.heappush(que, (0, start))
    cost[start] = 0

    # 우선순위 큐가 빌 때까지 반복
    while que:
        distance, city = heapq.heappop(que) # 현재 city와 거리를 가져옴

        # 현재 거리보다 현재 city를 최소 비용으로 갈 수 있는 방법이 있다면
        if -1 < cost[city] < distance:
            continue

        for next in graph[city]:
            weight = distance + next[1] # 현재 city를 걸치고 next[0]로 가는 비용

            # 현재 알고 있는 최소 비용을 업데이트 할 수 있다면
            if weight < cost[next[0]] or cost[next[0]] == -1:
                cost[next[0]] = weight
                heapq.heappush(que, (weight, next[0])) # 우선순위 큐에 추가

if __name__ == '__main__':
    city_count = int(sys.stdin.readline())
    bus_count = int(sys.stdin.readline())
    cost = [-1 for _ in range(city_count + 1)] # 최소 비용을 담는 리스트

    # graph input
    graph = [[] for _ in range(city_count + 1)]
    for _ in range(bus_count):
        s, e, w = map(int, sys.stdin.readline().split())

        graph[s].append([e, w])

    start, end = map(int, sys.stdin.readline().split())

    # computing
    dijkstra(start)

    # print
    print(cost[end])