[BOJ] 1916 최소 비용 구하기

N = int(input())
M = int(input())
graph ={i:[] for i in range(N+1)}
for i in range(M):
    node_x,node_y,fee = map(int,input().split())
    graph[node_x].append((node_y,fee))

start,end = map(int,input().split())
INFS = float('inf')
min_fees = [INFS] *(N+1)
visted = [0]*(N+1)
min_fees[start] = 0
visted[start] = 1
result = 0
node = start
while node != end:
    visted[node] = 1
    for next_node,fee in graph[node]:
        min_fees[next_node] = min(min_fees[next_node],min_fees[node]+fee)

    next_min_fees = INFS
    next_min_nodes = -1
    for ind in range(N+1):
        if not visted[ind] and next_min_fees > min_fees[ind]:
            next_min_fees = min_fees[ind]
            next_min_nodes = ind
    node = next_min_nodes


print(min_fees[end])

다익스트라 알고리즘을 이용한 문제이다.

heapq를 사용하지 않는 방식으로,

목적지로 생각되는 end가 나올때까지 반복을 하는것이다.

기본 원리는 다음과 같다.

노드와 같은 개수의 비용 리스트와 방문 리스트를 만들어준다.

그리고 비용 리스트는 무한대(큰 수)로 초기화 해주고, 출발지만 0으로 만들어준다.

방문리스트도 출발지만 방문표시로 바꿔준다.

 

그리고 난뒤에 출발지 노드와 인접한 노드들의 비용을 갱신해준다.

그리고 전체 노드를 돌아보면서, 방문하지 않았고, 최소비용인 노드를 다음노드로 선택해준다.

 

위와 같은 방식을 계속 반복해주면 된다.

 

 

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
graph =[[] for i in range(N+1)]
for i in range(M):
    node_x,node_y,fee = map(int,input().split())
    graph[node_x].append((node_y,fee))

start,end = map(int,input().split())
INFS = float('inf')
min_fees = [INFS] *(N+1)
node_list = []
heapq.heappush(node_list,(0,start))
min_fees[start] = 0
while node_list:
    cu_distance, node = heapq.heappop(node_list)
    if min_fees[node] < cu_distance:
        continue
    for next_node,fee in graph[node]:
        if fee + cu_distance < min_fees[next_node]:
            min_fees[next_node] = fee + cu_distance
            heapq.heappush(node_list,(min_fees[next_node],next_node))
print(min_fees[end])

heapq를 이용한 풀이방식이다.