[알고리즘|파이썬] 백준 1916 최소비용 구하기

문제 링크: https://www.acmicpc.net/problem/1916

 

📌 문제 탐색하기

시간 제한: 0.5 초
메모리 제한: 128 MB

 

✏️ 구해야 하는 정답

N개의 노드, M개의 엣지가 주어지고, 각 엣지에는 가격이 매겨진다. 시작, 종료 노드가 주어졌을때 최소 비용을 구하시오.

 

조건

- 1 ≤ N ≤ 1,000

- 1 ≤ M ≤ 100,000

- 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수

 

---

📌 풀이하기 

예시 1.

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

그림으로 나타내면 아래와 같다.

1️⃣ 그래프를 인접 리스트 형태로 표현

주어진 M개의 버스 정보를 기반으로 단방향 그래프를 구성한다.

인접 리스트(Adjacency List)를 사용하여 그래프를 저장한다.

graph[A] 리스트에 (B, 비용) 형태로 저장하여 출발 도시 A에서 도착 도시 B까지 가는 비용을 나타낸다.

 

2️⃣ 다익스트라 알고리즘 적용

다익스트라 알고리즘을 사용하여 출발 도시에서 각 도시까지의 최소 비용을 구한다.

우선순위 큐(힙, heapq)를 활용하여 가장 적은 비용의 노드를 우선 탐색한다.

거리 정보(distance[])를 유지하며 더 작은 비용이 발견되면 갱신한다.

최종적으로 distance[end] 값을 출력하면 최소 비용을 구할 수 있다.

 

---

📌 코드 설계하기

1. N개의 도시와 M개의 버스 정보를 입력받는다.

2. 인접 리스트(graph[])를 만들어 (도착지, 비용) 형태로 저장한다.

 

다익스트라 함수 실행 

1. 최단 거리 테이블 (distance[])을 무한대(INF)로 초기화한다.

2. 우선순위 큐를 사용하여 비용이 작은 노드부터 탐색한다.

3. 현재 노드에서 갈 수 있는 모든 인접 노드를 확인하며 더 작은 비용으로 이동할 수 있으면 갱신한다.

4. 모든 노드를 탐색한 후, distance[end] 값을 출력한다.

---

📌 정답 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input().strip())
m = int(input().strip())

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

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

def dijkstra(start):
    INF = float('inf')
    distance = [INF] * (n + 1)
    distance[start] = 0
    pq = [(0, start)]
    
    while pq:
        cost, node = heapq.heappop(pq)
        
        if distance[node] < cost:
            continue
        
        for next_node, price in graph[node]:
            new_cost = cost + price
            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))
    
    return distance

min_cost = dijkstra(start)[end]
print(min_cost)