[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)

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

풀이

방향성이 있는 그래프에서 start 도시에서 end 도시로 가는 최소 비용을 구하는 문제이다. 즉 다익스트라를 이용해야한다.

가중치가 있는 간선들이 주어지며, 음의 간선이 없다.

인접리스트와 최단거리 테이블을 초기화 하기 위해서 다음과 같이 초기화 한다.

adj = [[] for _ in range(N + 1)]  # 인접 리스트
distance = [INF] * (N + 1)  # 최단거리 테이블 초기화

도시 번호는 1부터 시작하므로 N + 1 크기로 배열을 잡고, INF는 초기 거리를 무한대로 세팅한다.

간선 정보 저장을 위해서 다음과 같이 정의 한다.

for _ in range(M) :
    u, v, cost = map(int, input().split())
    adj[u].append((v, cost))

u → v 로 가는 간선이 있고 비용은 cost이다.

다익스트라 알고리즘은 다음과 같이 정의한다.

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 시작점: 비용 0
    distance[start] = 0

    while q:
        dist, node = heapq.heappop(q)

        if distance[node] < dist:
            continue  # 이미 더 짧은 경로가 있으면 무시

        for next in adj[node]:
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))

heapq를 이용해서 우선순위 큐 기반 다익스트라를 진행하며, 현재 노드를 기준으로 인접한 노드의 거리 값을 갱신해 나간다.

코드

# 백준 1916 - 최소비용 구하기
# 분류 : 최단거리

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

N = int(input())
M = int(input())
adj = [[] for _ in range(N + 1)]
distance = [INF] * (N + 1)

for _ in range(M) :
    u, v, cost = map(int, input().split())
    adj[u].append((v, cost))

start, end = map(int, input().split())

def dijkstra(start) :
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q :
        dist, node = heapq.heappop(q)
        if distance[node] < dist :
            continue
        for next in adj[node] :
            cost = distance[node] + next[1]
            if cost < distance[next[0]] :
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))
    
dijkstra(start)

print(distance[end])