성능 요약
메모리: 125732 KB, 시간: 228 ms
분류
데이크스트라, 그래프 이론
문제 설명
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째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
아이디어, 문제풀이
- 힙을 활용한 다익스트라 기본 문제
- 인접리스트에 저장해 풀이하는게 좋다.
- 출발점과 도착점이 주어지고, 그 구간의 최소비용을 구하는 문제를 접했을땐 다익스트라를 떠올리는게 좋다.
TROUBLE SHOOTING
-
문제 자체가 매우 직관적으로 모든 조건들을 언급해 주기 때문에, 어렵지 않게 다익스트라의 가장 기본적인 개념으로 풀어낼 수 있다. 주의해야 하는점은 초기값을 무한대로 정해주어야 한다는것! 그리고 아래코드의 result와 같은 역할을 하는 임의의 배열에 계속해서 최소값을 갱신해준다고 생각해야한다.
-
추가적으로 알아야 하는건, graph[a].append((c, b)) 내 코드에서 c가 비용에 관련된 변수 였는데, c를 앞쪽에 선언해주어야 한다. heap을 사용해 구현할 경우 자동으로 최소가 루트에 오게 되는데, 그 루트의 정렬이 배열중 가장 앞쪽의 갚으로 자동 정렬되기 때문이다. 예를들어 (b,c)로 하게 된다면, 도착지점을 중심으로 heap에 저장하는 꼴이 되기 때문에, heap을 사용해 다익스트라를 구현할 거라면 꼭 주의해야한다!
코드
#https://www.acmicpc.net/problem/1916
#최소비용 구하기
#1916
import heapq
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((c, b))
start, end = map(int, input().split())
# print(graph)
# visit = [0] * (n+1)
result = [[] for _ in range(n+1)]
def dijkstra(graph, start, end):
result = [float('INF')] * (n+1)
# result[start] = 0
heap = []
heapq.heappush(heap, (0, start))
while heap:
dist, root = heapq.heappop(heap)
#루트가 end라면 끝내버리고 다시 while문을 돌림 / 시간아끼기
if root == end:
break
for range, node in graph[root]:
new_dist = dist + range
#더 작은값만 추가해 주기 위해서. 더 작다면 그 노드에 new_dist를 추가해줌
if new_dist < result[node]:
result[node] = new_dist
heapq.heappush(heap, (new_dist, node))
# print(heap)
return result[end]
answer = dijkstra(graph, start, end)
print(answer)