[백준] 5972 택배 배송

문제 설명

문제 링크

해당 문제는 가중치가 있는 그래프에서의 최단 거리를 구하는 문제이기 때문에 바로 다익스트라 알고리즘을 떠올리면 된다.

정점과 간선의 개수가 N과 M으로 주어지며, 시작점은 늘 1, 도착점은 늘 N이다.

문제 풀이

우선순위 큐를 이용해서 풀어야 하기 때문에 heapq를 사용한다.
다익스트라 알고리즘을 사용하여 최단 거리 문제를 풀 때는 두 개의 배열이 필요하다. 하나는 인접 행렬 또는 인접 리스트 형태의 정점과 간선을 표현하는 그래프이며, 하나는 시작점에서 해당 정점으로의 최단 거리(이 문제의 경우에는 최소 비용)를 나타내는 배열이다.

본 문제에서는 무조건 정점 1에서부터 시작하기 때문에 1에서 다른 정점들로 가는 데에 있는 최소 소의 수를 배열에 최신화해준다.

처음에는 모든 칸을 무한대로 초기화해준다.

2	3	4	5	6	7	8
INF	INF	INF	INF	INF	INF	INF

이후, 하나씩 검사하여 갱신해주면 된다.
우선 직접적으로 연결되어 있는 모든 정점으로의 가중치를 채워준다.

2	3	4	5	6	7	8
1	INF	4	INF	INF	INF	INF

2	3	4	5	6	7	8
1	INF	4	INF	INF	INF	INF

코드

import sys
import heapq 
INF = float("inf")
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)] 
cows = [INF]* (N+1)
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

def dijkstra(start):
    q = []
    cows[start] = 0
    heapq.heappush(q, (0, start))
    while q:
        cow, cur = heapq.heappop(q)
        if cows[cur] < cow:
            continue
        for next in graph[cur]:
            cost = cow + next[1]
            if cost < cows[next[0]]:
                cows[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))
    return cows[N]

print(dijkstra(1))"

---