최소비용 구하기 2
문제
n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.
입력
첫째 줄에 도시의 개수 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
3
1 3 5문제 해석
[백준]1504번: 특정한 최단 경로에서 다익스트라에 대해 자세히 설명해 놓았다. 다익스트라를 이용하면 문제의 50프로를 푼 것이나 마찬가지이지만, 문제는 최단 비용의 루트를 출력하는 것이다. 최단 비용 루트의 리스트를 따로 선언해서 최단 비용이 업데이트 될 때마다 루트 리스트에 초기화 해주고 새로 넣어주는 식으로 한다면 쉽게 풀 수 있다.
풀이
- 입력 값들을 받고 다익스트라 알고리즘을 이용하기 위해 초기 설정들을 해준다.
- 다익스트라 함수 선언
- 거리 비용, 현재 노드를 heap에서 빼준다.
- 그렇다면 가장 가까운 거리를 가진 것이 제일 먼저 빠질 것이다.
- 힙이 빌 때까지 돌면서 뽑아낸 거리 비용과 도착 노드를 이용해 비교를 해본다.
- 만약 뽑아낸 거리가 현재 업데이트 된 거리보다 크다면 업데이트를 할 필요가 없기 때문에 생략시킨다.
- 그게 아니라면 현재 노드가 갈 수 있는 노드들을 탐색한다.
- now 노드가 i[1]까지 한번에 갈 수 있는 거리를 dist와 더해준 것을 cost에 넣어준다.
- 이게 무슨 말이냐면 dist는 now 노드까지 갈 수 있는 거리중에 지금까지 최단 비용이다. 거기에 now 노드까지 한번에 갈 수 있는 거리를 더해서 만약 distance 리스트에 저장된 값보다 작다면 출발 노드에서 now 노드를 거쳐서 i[0] 노드에 가는 것이 비용이 더 작다는 얘기이기 때문에 최단 비용들을 저장해둔 distance 리스트에 업데이트 해준다.
- 여기서 i[0] 노드라는 것은 now 노드가 갈 수 있는 노드들 중 하나라는 뜻이다.
- 만약 업데이트가 되었다면 최단 비용이 나오는 루트가 달라졌다는 것이기 때문에 최단 비용 루트를 저장해둔 distance_root를 초기화 해주고 now 노드까지 거쳐온 노드들을 루프를 통해 넣어준다.
- 그리고 마지막으로 i[0] 노드를 넣어준다.
- 예를 들어보자. 만약 now 노드가 4이다.
- 4번 노드까지 거리가 1이며 이게 최단 비용이다.
- 그러면 4번 노드가 갈 수 있는 노드들을 탐색하며 4번 노드에서 한번에 갈 수 있는 비용을 4번 노드까지 오는데 걸린 비용인 (dist)
를 더해본다. 그렇게 해서 distance 배열에 저장된 것 보다 작다면 4번 노드를 거쳐서 i[0]번 노드에 가는 것이 더 비용이 싸다는 얘기이다. 그러면 비용을 업데이트 해주고 루트도 바뀌는 것이기 때문에 루트도 업데이트를 해준다. - 해당 경로 루트를 초기화 시켜주고 4번 노드까지 최단 비용인 경로들을 루프를 돌면서 넣어주고, 마지막으로 i[0]번 노드를 넣어준다.
- 그렇게 되면 경로는 1번에서 4번까지 최단 비용으로 오는 루트들이 저장되고 마지막으로 i[0]번 노드가 저장될 것이다.
- 그러고 나서 heap에 다시 넣어주어서 이 과정들을 반복한다.
- 그렇게 되면 마지막에 distance_root 리스트에는 출발 노드에서 각 노드까지 최단 비용으로 갈 수 있는 경로들이 저장되어 있을 것이다.
import sys
import heapq
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]
INF = 10 ** 9
distance = [INF] * (n + 1)
distance_root = [[] for i in range(n + 1)]
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append((b, c))
start, end = map(int, sys.stdin.readline().split())
def dijkstra(start, end):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
distance_root[start].append(start)
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
distance_root[i[0]] = []
for j in distance_root[now]:
distance_root[i[0]].append(j)
distance_root[i[0]].append(i[0])
heapq.heappush(q, (cost, i[0]))
dijkstra(start, end)
print(distance[end])
print(len(distance_root[end]))
for i in distance_root[end]:
print(i, end = " ")고찰
- 나는 1 4 5가 출력이 되어서 34 번째 줄 cost < distance[i[0]]를
<이 아닌 <= 으로 바꿔서 1 3 5 로 출력하게끔 하였다. - 그렇게 되면 같은 cost를 가지고 있더라도 업데이트가 계속 되는데 그러면 시간초과가 뜸.
- 스페셜 저지라고 붙어있는데 답이 여러 개 일수도 있다는 뜻임.
- 그렇다면 1 3 5로 나와도 정답이고 1 4 5 로 나와도 최단 경로이기 때문에
정답이 됨. - 근데 억지로 1 3 5를 만들려고 같은 cost도 루프에 참여하게끔
한다면 쓸데없는 경로 계산을 하기 때문에 시간초과가 뜸
