[BOJ/PYTHON] 11779. 최소비용 구하기 2 (최단 경로 - 다익스트라)

백준 문제 링크: https://www.acmicpc.net/problem/11779

문제 요약

A번째 도시에서 B번째 도시로 가는 최소비용과 경로 구하기

핵심 아이디어

문제를 읽으며 도시가 정점, 버스가 간선, 버스 비용은 가중치라는 것을 파악하면 된다!

비용이 양수라 다익스트라로 풀면 된다.

‘경로’ 구하는 게 필요했는데, 애초에 최단거리 갱신할 때 경로 정보도 같이 넣어주면 된다.

다익스트라 함수를 돌리며 현재 보는 노드가 ‘도착 도시’일 때 해당 값을 출력하면 된다.

풀이

# gold3-11779. 최소비용 구하기 2

import sys, heapq
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((b, c))
start_city_num, end_city_num = map(int, input().split()) # 구하고자하는 구간 출발점의 도시 번호, 도착점의 도시 번호
INF = int(1e9)
distance = [INF] * (n+1)

def dijkstra(start, end):
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start, [start]))
    while q:
        dist, now, path = heapq.heappop(q)
        if now == end: return dist, path # 최소비용, 경로
        if distance[now] < dist: continue        
        for next_node, next_dist in graph[now]:
            cost = distance[now] + next_dist
            if distance[next_node] > cost:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node, path + [next_node]))

min_cost, city_path = dijkstra(start_city_num, end_city_num)
print(min_cost)
print(len(city_path))
print(*city_path)

Trouble Shooting

경로 정보를 어디에서 구해야할지 고민을 하며 이것저것 출력해 봤는데 애초에 힙에 넣을 때 같이 넣어주면 되는 거였다!

실행 시간

메모리 65700KB, 시간 268ms (python3)