Baekjoon [5972] 택배배송 - python

문제

5972번: 택배 배송

 

코드 풀이

import heapq

n,m = map(int,input().split())
INF = int(1e9)
linked_list = [[] for _ in range(n+1)]

for i in range(m):
    node1,node2,cost = map(int,input().split())
    linked_list[node1].append((node2,cost))
    linked_list[node2].append((node1,cost))

distance = [INF] * (n+1)
# print(distance)
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in linked_list[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(1)
# print(distance)
if distance[n] == INF:
    print(-1)
else:
    print(distance[n])

 

문제 접근

기본적인 다익스트라 알고리즘이다.

1. 먼저 링크드리스트 또는 인접행렬을 통해 노드간 간선 비용을 저장한다.

2. 간선 비용을 최소화 할 수 있게 distance 변수로 모든 간선 비용을 최대값으로 설정한다.

3. 시작지점으로부터 다익스트라 알고리즘을 시작한다.

3-1. 최소힙을 유지하는 python의 heapq모듈을 사용하여 노드간 정보를 담아온다.

3-2. heapq에서 정보값을 하나씩 추출하면서 추출한 노드의 인접 노드간의 간선 정보를 계산한다.

3-3. 노드 간선 정보값 비교를 통해 값이 작다면 distance 변수값을 바꿔준다.

4. 3-1,3-2,3-3 을 지속적으로 반복한다.