[ 백준 ] 5972번 : 택배 배송 (파이썬)

문제 )

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

5972번: 택배 배송

 

[ 풀이 IDEA ]

- 다익스트라(Dijkstra) 알고리즘을 이용해서 문제를 해결하였다.

다익스트라 알고리즘은 최소 힙(heapq) 이용해서 풀어주면 좋다는거!! 꼭 기억하자

1️⃣ 초기화 사항 

=> 시작점으로 부터의 거리 list(distance), heapq 정의

2️⃣ [시작 점(start) 👉 최소 힙에서 추출한 점(node) 👉 해당 점(node)와 연결된 다른 점(nnode)] 으로 가는 최소거리를 구한다

Distance[nnode] = min(Distance[nnode], 시작점(start)에서 현재 점(node)까지 가는 거리 + 현재 점(node)에서 연결된 점(nnode)로 가는 거리)

 

 

- python code 

import heapq
import sys
input = sys.stdin.readline
INF = 1e9

def solution(road_info, start, end):
    q = []  # 최소 힙
    heapq.heappush(q, (0, start))

    distance = [INF] * (n+1)	# start에서부터 해당 노드까지 가는 최소 거리
    distance[start] = 0

    while q:
        cost, node = heapq.heappop(q)
        if node == end:
            return distance[node]

        # next와 연결된 곳 구하기
        for ncost, nnode in road_info[node]:
            if ncost + cost < distance[nnode]:
                distance[nnode] = ncost + cost
                heapq.heappush(q, (cost + ncost, nnode))


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

print(solution(road_info, 1, n))