[백준✨] 11779번 <최소비용 구하기2> / Python 문제풀이 / 다익스트라

해답)

import heapq
import sys

def input():
    return sys.stdin.readline().rstrip()

'''
 입력받는 과정
'''
N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    fr, to, cost = map(int, input().split())
    graph[fr].append((to,cost))

FROM, TO = map(int, input().split())

'''
 변수 설정
'''
distance = [float('inf') for _ in range(N+1)] # 거리
path = [[] for _ in range(N+1)] # 경로를 담을 배열
path[FROM].append(FROM)
q = [(0,FROM)] # 다익스트라를 쓸 우선순위 큐
heapq.heapify(q)


'''
 다익스트라를 이용한 알고리즘
'''
while q:
    now_cost, now = heapq.heappop(q)
    if now_cost > distance[now]:
        continue
    if now == FROM:
        distance[now] = 0
    for next, next_cost in graph[now]:
        path_cost = next_cost + now_cost
        if path_cost < distance[next]:
            distance[next] = path_cost
            heapq.heappush(q, (path_cost, next))
            # path 가 갱신됐을 때 현재까지의 경로를 넣어준다.
            path[next] = []
            for p in path[now]:
                path[next].append(p)
            path[next].append(next)

print(distance[TO])
print(len(path[TO]))
print(' '.join(map(str,path[TO]))) # 경로 출력

---

풀이)

다익스트라를 이용한 최단경로 문제입니다.

하지만 최소비용의 경로 또한 담아줘야 하는 특이점이 있습니다. 🤔

 

저는 path 라는 배열을 가지고, 해당 노드까지 도달하는데에 걸린 path들을 모두 저장하게끔 하였습니다.

 

예시)

다익스트라를 통해

 1의 노드에서 3의 노드 까지의 길이 최단인 것을 안 상황?

   기존 : 큐에 3의 노드와, 그때의 최솟값을 넣는다.

   내 코드 : 큐에 3의 노드와, 그때의 최솟값을 넣고, 3의 path를 [1의 노드까지의 path, 노드3] 로 갱신해준다.

 

이 방법을 통해 특정 노드까지의 path 를 지속적으로 갱신해줍니다.

 

 

---

path 배열이 매번 새롭게 갱신되는 상황이 있을 거 같아 다른 레퍼런스를 찾아보니, 더 좋은 방법이 있더군요.

 

굳이 path 배열을 매번 번거롭게 갱신하는 대신, path 배열값을 최소경로의 이전 노드 하나만(그 전에 어디 노드에서 왔는지)을 저장해두면, 마지막에 recursive 하게 최소경로를 역추적할 수 있습니다.

(참고 : hazung.tistory.com/145?category=835203)  

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.