[백준-파이썬] 11779: 최소 비용 구하기2

문제 보러 가기!

평범한 다익스트라 + 알파이다.
최소 비용을 가지는 경로를 방문 도시 순서대로 출력하는 부분, 그 경로에 포함되는 도시 개수도 출력해야 해서 좀 더 생각해야 했다.
distance 리스트를 활용했다. 평범한 다익스트라에서는 distance 리스트는 출발점에서 그 점까지의 비용만 저장한다. 그런데 여기에서는 출발점에서 그 점까지 최소 비용으로 올 때, 그 전 점도 저장했다!

다익스트라를 다 수행한 후에, 최종 도착 점부터 distance 리스트를 활용해서 거꾸로 봐주었다. 그 전에 어떤 점에서 왔는지를 봐서 history 리스트에 저장한 후, 거꾸로 출력했다.

[TMI 잠깐 근황]

요즘 싸피에서 프로젝트를 열심히 하느라고 ㅠㅠ 문제를 별로 못풀다가 푸니까 재밌다 >< (물론 프로젝트도.. 재미있다.. 모르는 게 엄청 많다는 걸 매 순간 깨닫고, 공부하고 있다... 어려운 React와 TypeScript의 세계.. 화이팅!)

코드 😁

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())

city_cnt = int(input())
bus_cnt = int(input())

graph = [[] for _ in range(city_cnt + 1)]
distance = [[INF, 0] for _ in range(city_cnt + 1)]  # 출발점부터 그 점까지 비용, 최소 비용으로 그 점에 오려면 그 전에 어디에서 오는지

for _ in range(bus_cnt):
    start, finish, cost = MIIS()
    graph[start].append((finish, cost))

start_city, target_city = MIIS()

# 다익스트라
q = []
heapq.heappush(q, (0, start_city))
distance[start_city] = [0, -1]

while q:
    dist, idx = heapq.heappop(q)
    if distance[idx][0] < dist:
        continue

    for finish_idx, cost in graph[idx]:
        now_cost = dist + cost
        if now_cost < distance[finish_idx][0]:  # 거쳐 가는 경우
            distance[finish_idx][0] = now_cost
            distance[finish_idx][1] = idx
            heapq.heappush(q, (now_cost, finish_idx))

print(distance[target_city][0])

# 지나온 경로 찾기
history = [target_city]
after_city = distance[target_city][1]
while True:
    if after_city == -1:
        break
    else:
        history.append(after_city)
    after_city = distance[after_city][1]

print(len(history))
print(' '.join(map(str, history[::-1])))