(Python) - BOJ(11779번) : 최소비용 구하기 2

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

---

• 문제 : 

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

 

 

 

---

• 풀이 :

다익스트라의 기본 개념에 추가로 경로를 출력하는 문제입니다.

다익스트라의 기본 개념은 여기 에서 설명하였으므로 따로 언급하지는 않겠습니다. 

 

추가적인 아이디어로 경로를 담아줄 path라는 배열을 사용하였습니다.

path라는 배열은 자신의 부모 노드, 즉 최단거리로 접근할 때 어디로부터 왔는가에 대한 정보가 담겨있습니다.

trace라는 함수를 사용하여 end에서부터 start가 나올 때까지 역으로 추적하였고 이 결과물을 뒤집어서 출력하면 경로가 나옵니다.

 

 

 

---

• 소스코드 : 

import sys
from heapq import heappush,heappop
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,end = map(int,input().split())
heap = []
heappush(heap,[0,start])
distance = [float("inf") for _ in range(N+1)]
distance[start] = 0
path = [None for _ in range(N+1)]
def trace(start, end):
    res = [end]
    path[start] = 0
    while path[end]:
        res.append(path[end])
        end = path[end]
    return res[::-1]

while heap:
    cost,curr = heappop(heap)
    if distance[curr] < cost:
        continue
    for next,c in graph[curr]:
        totalCost = cost + c
        if distance[next] > totalCost:
            heappush(heap,[cost+c,next])
            distance[next] = totalCost
            path[next] = curr
print(distance[end])
answer = trace(start,end)
print(len(answer))
print(" ".join(map(str,answer)))