[Python 파이썬] 백준 5972번 - 택배 배송

2024년 9월 26일

문제 링크 : 백준 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가 주어집니다.

출력

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

 

알고리즘 분류

• 그래프 이론
• 최단 경로
• 데이크스트라

---

 

문제 접근

 

1번 노드에서 N번 노드까지 최소한의 비용으로 가야하므로 다익스트라 알고리즘을 활용하면 되겠다 판단하였다.

 

간선의 개수는 최대 50,000개이며 간선의 가중치는 최대 1,000이므로 특정 노드까지 도달하는데 최악의 경우 50,000 * 1,000 만큼의 비용이 필요할 수 있다.

그러므로 각 노드까지 도달하는데 필요한 최소 비용은 경로와 최소비용을 아직 모른다는 의미로 모두 50,000 * 1,000 + 1로 초기화 해주었다.

 

시작 노드인 1번 노드를 시작 노드로 모든 정점에 대해 다익스트라를 활용해 탐색을 진행하며 최소 비용을 구하고,

로직이 끝났을 때 N번 노드까지의 최소 비용을 출력하면 되는 문제이다.

---

입력 예제

 

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

 

 

---

전체 코드

 

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

def dijkstra(start_v):
    queue = deque()

    INF = 50000 * 1000 + 1
    costs = [INF for _ in range(N + 1)]

    queue.append(start_v)
    costs[1] = 0

    while queue:
        now_v = queue.popleft()
        next = graph[now_v][:]
        while next:
            next_v, cost = next.pop()
            if costs[now_v] + cost < costs[next_v]:
                costs[next_v] = costs[now_v] + cost
                queue.append(next_v)

    return costs[N]



if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        v1, v2, c = map(int, input().split())
        graph[v1].append([v2, c])
        graph[v2].append([v1, c])
    
    print(dijkstra(1))

 

---

풀이 후기

 

다익스트라를 활용하여 풀 수 있는 문제였다.