[baekjoon] 백준 1916번 : 최소비용 구하기(by python 파이썬) 다익스트라 최단거리

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

1916번: 최소비용 구하기

 

정답 code

# 최소비용 구하기
import heapq
import sys
input = sys.stdin.readline
INT = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    visit = [INT] * (n+1)
    visit[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if visit[node] >= dist:
            for node_index, node_time in bus[node]:
                time = node_time + dist
                if visit[node_index] > time:
                    visit[node_index] = time
                    heapq.heappush(q,(time,node_index))
    return visit

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    s,e,t = map(int,input().split())
    bus[s].append((e,t))

start,target = map(int,input().split())
result = dijkstra(start)
print(result[target])

 

solution

단순한 최단거리 문제다. 다익스트라를 이용하여 간단히 해결 할 수 있다.

골드 문제지만 다익스트라를 익혔다면 실버 정도로 생각되는 문제다.

 

다익스트라 알고리즘:

1. 출발노드 설정

2. 출발노드 기준으로 각 노드의 최소비용 저장

3. 방문하지 않은 노드중 비용이 가장 적은 노드 선택

4. 해당 노드에서 특정 노드로 가는 최단거리 확인후 갱신

5. 3~4 반복