[BOJ/Python] 1916_최소비용 구하기

문제 출처:https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

예제 입력 1

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1

4

 

---

풀이

 

도시를 노드라고 생각하고 도시와 도시를 연결하는 버스를 간선이라고 생각할 수 있다.

그렇다면 버스의 비용은 간선의 가중치이고, 최소 비용을 구하기 위해서 출발지 노드로부터 목적지 노드까지의 간선의 가중치의 합이 최소가 되어야 한다.

 

양의 가중치만 존재하므로 다익스트라 알고리즘(Dijkstra Algorithm)을 이용하여 문제를 해결할 수 있다.

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e9)
 
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
 
graph = [[] for _ in range(n+1)]
distance = [INF for _ in range(n+1)]
 
for _ in range(m):
    u,v,w, = map(int,sys.stdin.readline().split())
    graph[u].append((v,w))
 
start,end = map(int,sys.stdin.readline().split())
 
def dijkstra(start,end):
    queue = []
    heapq.heappush(queue,(0,start))
    distance[start] = 0
    
    while queue:
        dist, node = heapq.heappop(queue)
 
        if node == end:
            return dist
 
        if dist > distance[node]:
            continue
 
        for i in graph[node]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue,(cost,i[0]))
 
print(dijkstra(start,end))

1. 노드와 간선의 정보를 입력받을 graph라는 리스트를 만든다.
2. 출발지로부터 각 노드의 최소 거리를 저장할 distance를 만들고, INF 값(이론상 무한, 여기서는 1e9의 값)으로 초기화한다.
3. graph의 경우, 각 노드의 index마다 연결되어 있는 다른 노드와 가중치의 정보가 들어있다.
4. dijkstra 함수의 경수, heapq모듈을 import하여 우선순위 큐를 이용하여 구현한다.
5. 출발 노드에서 출발 노드까지의 거리를 0이라고 설정하고, 큐에 거리와 노드의 정보를 넣는다.
6. 큐에 원소가 존재할 동안 while문을 통해 반복한다.
7. 큐에 있는 원소를 꺼낸다. (우선순위 큐는 최소힙으로 구현되어있으므로, 큐에 있는 원소들 중, 거리가 가장 짧은 원소가 나오게 된다.)
8. 만약 지금 꺼낸 노드의 거리가 저장되어있는 노드의 거리보다 크다면 continue를 이용하여 다음 원소를 꺼낸다. (이미 최단 거리를 구한 노드이다.)
9. 만약 그게 아니라면, 그 노드와 연결되어있는 노드들을 하나씩 꺼내, 현재 노드를 거쳐갔을 때의 거리와 저장되어 있는 거리를 비교한다.
10. 현재 노드를 거쳐갔을 때의 거리가 cost이고, 만약 거쳐갔을 때의 거리가 더 짧다면 해당 노드의 출발지로부터의 거리를 cost로 바꾸고, 큐에 (cost, 해당노드)를 push 해준다.
11. 그리고 만약 현재 노드가 end(도착지)라면, 현재 출발지로부터 현재 노드까지의 거리를 return 한다.