[G5] 백준 1916 - 최소비용 구하기 (Python3)
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
해결방법
다익스트라 알고리즘을 이용한다.
풀이👀
입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다.
각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지만 단순히 이 문제를 해결 할 수 있는 것이 아니다. 그래서 이런 문제에 특화된 다익스트라 알고리즘을 사용하는 것이다.
코드🐱👓
import heapq
N = int(input()) # 도시의 개수
M = int(input()) # 버스의 개수
graph = {i: [] for i in range(1, N + 1)}
# 버스의 정보 입력
for _ in range(M):
st, desti, cost = map(int, input().split())
graph[st] += [(cost, desti)]
start, destination = map(int, input().split()) # 출발 도시, 도착 도시
distances = {node: float('inf') for node in graph}
distances[start] = 0
visited = [0] * (N + 1)
queue = []
heapq.heappush(queue, [distances[start], start])
while queue:
current_distance, current_node = heapq.heappop(queue)
if distances[current_node] < current_distance or visited[current_node]:
continue
visited[current_node] = 1 # 방문 표시
for next_distance, next_node in graph[current_node]:
distance = current_distance + next_distance
if distance < distances[next_node]:
distances[next_node] = distance
heapq.heappush(queue, [distance, next_node])
print(distances[destination])
heappush 코드 설명
(heappush가 어떻게 동작하는지에 대한 상세한 기술이 아니라, heappush를 할 때 list를 넣었다. 이 list의 원소는 순서가 정해져 있기 때문에 이 코드에 대한 설명을 하려는 것이다.)
우선순위 큐를 이용해서 문제를 해결하려 했다. queue 라는 리스트가 바로 우선순위 큐이다. 우선순위 큐는 힙(heap)이라는 자료구조를 바탕으로 한다. 이 힙을 구현하기 보다는 라이브러리를 사용했다. (Python 의 내장 라이브러리인 heapq는 최소힙이 기본 꼴이다.)
heappush는 heap의 말단에 노드를 추가하고, 추가한 노드의 부모노드와 비교해나가면서 부모노드보다 작은 수라면 자리를 바꾼다. 이것을 부모노드가 더 작은 수일 때까지, 또는 heap의 뿌리(root)로 갈때까지 반복한다.
그런데 내 코드는 heap안에 list를 넣고 있다. 이것 때문에 이 설명글을 쓰고 있다.
Python에서 리스트 간의 정렬(비교)을 할 때는 list의 첫 번째 원소부터 비교한다. 첫 번째 원소가 서로 같다면 두 번째 원소끼리, 두 번째 원소끼리도 같다면 세 번째 원소끼리, ... . 이런식으로 말이다. 이말은 즉슨 첫 번째 원소가 기준이 된다는 이야기이다.
그래서 우선순위의 기준을 (짧은)거리 순으로 정하기 위해서 queue에 heappush를 할 때 distances[start] 가 list의 첫 원소로 들어간 것이다.