백준 [1916 최소비용 구하기] 파이썬 풀이

📌 문제 탐색하기

• 간선 별로 가중치가 다르고, 음의 가중치가 없는 최단 거리 구하기 문제이다.
• 입력으로 도시(노드)의 갯수, 버스(간선)의 갯수, 버스 정보(출발점, 도착점, 가중치)가 주어진다.

💡 알고리즘 선택

• 가중치가 다르기 때문에 BFS는 사용할 수 없고, 다익스트라 알고리즘을 활용해야 한다.

📌 코드 설계하기

1. 문제의 input을 받음.

2. 버스 정보를 저장할 data 리스트를 만들고, 출발점을 인덱스로 하여 도착점과 가중치를 저장한다.

3. 다익스트라 알고리즘을 구현하고, 힙 자료구조를 활용하여 빠른 시간 안에 탐색을 마칠 수 있게 구현한다.

4. 도착점의 거리를 출력한다.

📌 시도 회차 수정 사항 (Optional)

1회차에 성공

 

📌 정답 코드

import heapq

n = int(input())
m = int(input())
INF = 1e8

data = [[] for _ in range(n+1)]
for i in range(m):
    start, end, cost = map(int, input().split())
    data[start].append((end, cost))

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

distance = [INF] * (n+1)

def dijkstra(start):
    distance[start] = 0
    heap = [(0, start)]
    
    while heap:
        cost, current = heapq.heappop(heap)
        if distance[current] < cost:
            continue
        
        for dest, cost in data[current]:
            new_cost = distance[current] + cost
            if distance[dest] > new_cost:
                distance[dest] = new_cost
                heapq.heappush(heap, (new_cost, dest))

dijkstra(start)
print(distance[end])