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

문제 보기

이 문제는 다익스트라 문제이다.

 

최근 코딩 테스트에서 자주 출제되는 유형이기 때문에 알아둘 필요가 있다고 생각한다. 

 

알고리즘 순서는 다음과 같다.

1. 입력(노드, 간선, 시작 지점, 도착 지점)을 받는다.

2. 1차원 배열에 거리의 값을 무한대로 초기화해서 저장한다. (시작 위치는 0으로 초기화한다.)

3. 우선 순위 큐를 사용해서 최단거리에 있는 노드를 선택하고 그 노드와 인접된 노드까지의 거리를 계산한다.

   - 이미 계산한 거리보다 더 작은 거리 값이 나온다면 값을 업데이트하고 인접한 노드를 우선순위 큐에 추가한다.

4. 우선순위 큐가 빌 때까지 3번 과정을 반복한다.

 

다익스트라를 구현하면서 왜 우선순위 큐를 사용하는지 궁금하였다. bfs 대신에 다익스트라를 구현했다는 자체만으로도 엄청난 시간을 단축했다고 생각하였다. 하지만 우선순위 큐를 사용하지 않으면 읽는 순서에 따라서 값 업데이트 수가 많을 수 있으며 굳이 하지 않아도 되는 연산들을 많이 하기 때문에 우선순위 큐를 활용해야 한다고 하였다.

코드

import sys
from heapq import heappush, heappop


def dijkstra(start, end):
    heap = []
    heappush(heap, (0, start))  # 시작지점 힙에 추가
    distance = [sys.maxsize] * (N + 1)  # 각 정점사이의 거리 무한대로 초기화
    distance[start] = 0  # 시작 지점 0으로 초기화

    while heap:
        weight, index = heappop(heap)
        for e, c in bus[index]:
            if distance[e] > weight + c:
                distance[e] = weight + c
                heappush(heap, (weight + c, e))
    return distance[end]


if __name__ == "__main__":
    # input
    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())  # 찾고자하는 비용 경로(출발지, 도착지)

    # print
    print(dijkstra(start, end))