[Baekjoon 1916 / python / 골드5] 최소비용 구하기

import heapq

import sys

INF = int(1e9)

input = sys.stdin.readline

N = int(input())  # 도시 개수 ( 노드 개수 )

E = int(input())  # 버스 개수 ( 간선 개수 )

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

for _ in range(E):

    a, b, c = map(int, input().split())  # 출발노드, 도착노드, 거리 입력받기

    graph[a].append([c, b])  # (거리, 도착노드)

start, end = map(int, input().split())  # 계산해야 할 출발지, 도착지

distance = [INF] * (N + 1)  # 최단 경로 리스트

def dijkstra(start):

    queue = []

    heapq.heappush(queue, (0, start))  # 시작 노드 거리(0)와 시작 노드 큐에 삽입

    distance[start] = 0 # 시작 노드의 최단 경로 초기화

    while queue:

        dist, here = heapq.heappop(queue)  # 큐에서 거리, 노드 빼기

        if distance[here] < dist:  # 기존최단경로가 방금뽑은거리보다 짧다면 패스

            continue

        for i in graph[here]:  # 방금뽑은노드의 인접노드에 대하여 반복

            cost = distance[here] + i[0]  # 방금뽑은거리 + 인접노드까지 거리를 계산

            if cost < distance[i[1]]:  # 계산한게 기존 인접노드까지의 최단경로보다 짧으면 테이블 갱신

                distance[i[1]] = cost

                heapq.heappush(queue, (cost, i[1]))  # 갱신했으니 거리와 노드 큐에 삽입

dijkstra(start)

print(distance[end])  # start부터 end까지의 최단경로 출력

 

다익스트라 알고리즘이 사용되는 문제이다.

 

그냥 다익스트라 알고리즘 코드를 때려 넣으면 바로 풀리는 쉬운 문제이다. 물론 다익스트라를 공부하는 것 자체가 문제지만...

 

다익스트라에 대한 정보는

https://yskisking.tistory.com/185

여기 내 블로그 글에서 보거나, 다른분들이 잘 정리해두신 글들이 많으니 찾아보길 추천한다.

다익스트라를 모르고 무작정 푸는 것 보다는 차라리 다익스트라를 공부한 후 푸는 게 오히려 시간도 아끼고, 기억에 오래 남는 효율적인 공부방법이 될 것이다. 다른 문제에 응용도 할 수 있고.