[BOJ][🟡5][백준#05972] 택배 배송

문제 출처

BAEKJOON Online Judge #5972

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다. 다음 지도를 참고하세요.

       [2]---
      / |    \
     /1 |     \ 6
    /   |      \
 [1]   0|    --[3]
    \   |   /     \2
    4\  |  /4      [6]
      \ | /       /1
       [4]-----[5] 
            3   농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다. 농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다. 둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

예제

입력

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

출력

5

My Sol

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
rels = [[] for _ in range(N+1)]
minns = [1e8]*(N+1)
minns[1] = 0
Q = deque([1])
for _ in range(M):
    u, v, k = map(int, input().split())
    rels[u].append((v, k))
    rels[v].append((u, k))

while Q:
    u = Q.popleft()
    for v, k in rels[u]:
        if minns[u]+k < minns[v]:
            minns[v] = minns[u]+k
            Q.append(v)

print(minns[N])

다익스트라 알고리즘을 사용해 최소 비용 경로를 구하는 문제였지만, 풀이가 생각이 나지 않아 효율적으로 풀지는 못했던 문제였다. 일단 기본 컨셉으로 문제를 풀긴 했지만, 방문했던 노드를 너무 자주 방문하는 구조이기 때문에 연산시간이 길게 나오는 풀이이다.

1. 입력을 받아 양방향 노드의 배열에 가중치와 함께 넣는다.
2. 해당 노드까지의 가중치 저장 배열인 minns를 1e8로 초기화한다. 최댓값은 5000만이며, 편의상 1억의 크기로 가중치를 초기화했다.
3. 시작노드인 1번 노드의 가중치인 minns[1]을 0으로 두고, 해당 노드부터 가중치만큼 더해 연결된 이웃 노드들의 현재 가중치 값과 비교해 현재 노드에서 출발하는 것이 더 효율적이라면 가중치 누적값을 갱신하고 Q에 넣는다.
4. 이를 Q가 빌 때까지 진행한다.

결과

맞았습니다!!

모범답안

출처

import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[]for _ in range(N+1)]
for _ in range(M):
    a, b, cost = map(int, input().split())
    arr[a].append((cost, b))
    arr[b].append((cost, a))


def dijkstra():
    q = []
    heapq.heappush(q, (0, 1))
    total = [sys.maxsize] * (N+1)
    total[1] = 0
    while q:
        cost, node = heapq.heappop(q)
        if node == N:
            return total[node]
        if total[node] < cost:
            continue
        for ncost, nnode in arr[node]:
            if cost+ncost < total[nnode]:
                total[nnode] = cost+ncost
                heapq.heappush(q, (cost+ncost, nnode))

print(dijkstra())

다익스트라를 정석적으로 사용하며 연산시간이 훨씬 짧은 풀이를 분석해보려 한다. 비결은 heap을 사용하여 가중치가 작은 연결부부터 저장한다는 것이다.

1. 초기화의 값은 sys.maxsize라는 값으로 설정한다.
2. 가중치인 cost를 기준으로 오름차순하는 heapq에 저장한다.
3. 가중치가 적은 노드와 연결부터 heappop하며 누적 가중치를 갱신해간다.
4. 노드가 처음으로 N을 바라보는, 즉 최소 경로로만 이동하며 N을 마주친 경우 가장 적은 가중치 누적값을 가지므로 이때의 total[node]를 출력한다.