알고리즘 :: 다익스트라(그래프 이론) 예제 1916 파이썬

다익스트라 알고리즘은 그래프 이론에서 주어진 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. (그래프 이론 + dp)

다익스트라 알고리즘 개요

다익스트라 알고리즘은 다음과 같은 단계로 동작합니다:

1. 출발 노드 선택: 시작 노드를 선택하고, 시작 노드의 최단 경로를 0으로 초기화합니다.
2. 우선순위 큐 활용: 출발 노드부터 갈 수 있는 모든 경로를 우선순위 큐(힙)에 넣습니다. 시작 노드의 최단 경로가 0이므로 시작 노드를 우선순위 큐에 넣습니다.
3. 최단 경로 갱신: 우선순위 큐에서 최소 비용의 노드를 꺼내서 해당 노드에서 갈 수 있는 모든 노드들의 최단 경로를 갱신합니다. 이 때, 기존 경로보다 더 짧은 경로를 발견하면 해당 노드의 최단 경로를 갱신하고 우선순위 큐에 추가합니다.
4. 목적지 도달: 우선순위 큐에서 목적지 노드에 도달하면 해당 노드의 최단 경로를 반환합니다.

 

백준 1916 :: 문제 해결 방법

주어진 문제에서는 다음과 같은 단계로 다익스트라 알고리즘을 적용할 수 있습니다:

1. 입력으로 주어지는 도시의 개수 N과 버스의 개수 M을 받습니다.
2. 각 버스의 정보를 인접 리스트 형태로 저장합니다. 이 때, 각 도시에서 다른 도시로 가는 데 필요한 비용을 저장합니다.
3. 출발점에서 도착점까지의 최소 비용을 구해야 하므로 다익스트라 알고리즘을 사용합니다. 출발점에서부터 다른 모든 도시까지의 최소 비용을 계산합니다.
4. 다익스트라 알고리즘을 통해 구한 최소 비용 중 도착점의 비용을 출력합니다.

from heapq import heappush, heappop
import sys
input = sys.stdin.read

n = int(input().strip())
m = int(input().strip())
table = [[] for _ in range(n + 1)]

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

s, e = map(int, input().strip().split())

def dijkstra(s, table):
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[s] = 0
    q = []
    heappush(q, (0, s))  # (비용, 노드)

    while q:
        current_cost, current_node = heappop(q)

        if dp[current_node] < current_cost:
            continue

        for next_node, next_cost in table[current_node]:
            new_cost = current_cost + next_cost
            if new_cost < dp[next_node]:
                dp[next_node] = new_cost
                heappush(q, (new_cost, next_node))

    return dp

result = dijkstra(s, table)
print(result[e])