1916: 최소비용 구하기

풀이 시간

• 12m
• dijkstra 알고리즘 이용

구현 방식 (Dijkstra 알고리즘)

• 출발점을 기준으로 초기화: 출발점에서 시작하여 모든 정점들까지의 거리를 무한대로 초기화. 출발점 자체의 거리는 0으로 설정
• 인접한 정점들의 거리 갱신: 현재 방문하지 않은 정점들 중에서 출발점으로부터 거리가 가장 가까운 정점을 선택하고, 해당 정점과 연결된 인접한 정점들의 거리를 갱신. (갱신할 때에는 현재까지 알려진 출발점으로부터의 거리와 해당 정점간의 가중치를 더한 값 중 작은 값을 선택하여 거리를 갱신함.)
• 위의 과정을 반복: 모든 정점들이 방문될 때까지 위의 과정을 반복. 매번 가장 가까운 정점을 선택하여 해당 정점과 연결된 인접한 정점들의 거리를 갱신하는 방식으로 진행됨.

Heap을 이용하여 구현

• distances (혹은 costs)를 시작 노드로 제외하고 무한대로 초기화 (시작 노드는 0으로 초기화)
• heapq를 이용하기 위해 heap에 원소를 [해당 노드의 cost, 해당 노드 번호] 이런식으로 넣음
• heap이 빌때까지 (모든 노드를 방문할 때까지) while문 반복
• 최단 거리가 가장 짧은 노드를 꺼내고, 해당 노드까지의 거리(curr_cost)가 costs에 기록된 거리보다 길다면 continue
• 그렇지 않다면 해당 노드를 거쳐가는 거리가 더 짧을 수 있기 때문에 인접한 노드들을 탐색
  -> curr_cost + next_cost (=cost, 해당 노드를 거쳐갈 때의 거리)가 costs에 기록된 거리(알고있는 거리)보다 작으면 costs[next_dest]를 cost로 갱신하고, 다음 인접 거리를 계산하기 위해 heap에 push

코드

import sys
import heapq


def dijkstra(start):
    costs[start] = 0

    heap = []
    heapq.heappush(heap, [costs[start], start])

    while heap:
        curr_cost, curr_dest = heapq.heappop(heap) # 최단 거리가 가장 짧은 노드를 꺼냄
        if costs[curr_dest] < curr_cost: # 기존에 있는 거리보다 길다면 볼 필요 없음
            continue

        for next_dest, next_cost in graph[curr_dest]:
            cost = curr_cost + next_cost # 해당 노드를 거쳐갈 때의 거리
            if cost < costs[next_dest]: # 알고있는 거리보다 작으면 갱신
                costs[next_dest] = cost
                heapq.heappush(heap, [costs[next_dest], next_dest]) #다음 인접 거리를 계산하기 위해 큐에 삽입


N = int(sys.stdin.readline()[:-1])
M = int(sys.stdin.readline()[:-1])
graph = [[] for _ in range(N+1)]
for m in range(M):
    start, end, cost = list(map(int, sys.stdin.readline()[:-1].split()))
    graph[start].append((end, cost))
    
costs = dict()
for i in range(1, N+1):
    costs[i] = int(10e9)

S, E = map(int, sys.stdin.readline()[:-1].split())
dijkstra(S)
print(costs[E])

결과