[백준] 최소비용 구하기 (골드 5) Python

 

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

 

접근 방법

N을 정점, M을 간선으로 하는 그래프를 그릴 수 있다. 또한 '버스 비용'이라는 가중치가 존재하는 그래프다. 즉, 가능한 경로 중에서 가중치의 합이 가장 적은 경로를 찾는 문제이다. 문제의 조건을 보면 '버스 비용이 0보다 크거나 같다'라는 힌트가 있다. 이는 다익스트라 알고리즘을 쓰기 위한 전제조건인 '가중치가 음수가 아니어야 한다.'라는 조건과 같은 말이다.  

결국, 이 문제는 다익스트라 알고리즘으로 풀 수 있다.

 

자세한 풀이 과정은 다음과 같다.

1. n+1 길이의 그래프(graph)를 그려준다.

2. 거리(가중치) 정보를 기록할 n+1 길이의 리스트 distance를 선언해준다. 이때 각 요소의 값은 모두 매우 큰 수인 1e9로 초기화해준다. 

3. 빈 리스트(q)를 선언하고, 출발점부터 출발점까지의 거리인 distance[start]는 0으로 만들어준다.

4. q를 힙으로 만드는데, 이때 가중치를 기준으로 자동으로 힙정렬되도록 (distance[start], start)의 형태로 넣어준다.

5. q가 다 없어질 때까지 반복문을 돈다. 이때 현재 확인 중인 정점과, 현재 정점 다음에 방문할 후보 정점들 중에서 가장 가까운 곳을 고른다. 이때 기존에 기록된 경로보다 가중치가 더 작은 경로를 발견한다면 distance를 업데이트해주고, q에 다시 삽입해준다.

6. 이렇게 하면 distance의 각 인덱스에는 해당 정점까지 걸리는 버스 비용이 저장되게 된다.

 

Python 코드

# 백준 1916 최소비용 구하기
# a에서 b로 가는 비용을 최소화.
from collections import defaultdict
import heapq

def dij(graph, start):
    q = []
    distance[start] = 0
    heapq.heappush(q, (distance[start], start))

    while q:
        dist, now = heapq.heappop(q)
        
        # 이미 방문했거나 최솟값이 아니면 continue
        if distance[now] < dist:
            continue

        for next_node, next_dist in graph[now]:
            cost = dist + next_dist # 총 이동거리

            # 현재 정보보다 더 적은 시간이 필요하다면 갱신
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
distance = [1e9] * (n+1)

for _ in range(m):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))

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

print(distance[end])