[백준]11779 - 최소비용 구하기 2 (#파이썬 #다익스트라 경로 찾기)

다익스트라로 최단 거리를 구하는 방식에서 경로 정보를 추가하는 로직!

11779번: 최소비용 구하기 2

 

다익스트라 알고리즘은 ‘특정 시작 지점’에서 ‘어떤 마지막 지점’으로 최소 비용으로 이동할 때의 '최소 비용'을 구할 수 있는 알고리즘이다.

 

그렇다면 경로 정보를 어떻게 추가할 수 있을까?

다익스트라에서 heap queue를 pop 했을 때 나오는 정보는 최단 거리 관련 정보라고 할 수 있다. 즉, 유의미한 정보이다. 여기에 경로 정보가 포함되도록 해야 한다.

path = [st]
hq.heappush(qu, [0, st, path])
while qu:

 

해당 코드를 보면 path 정보가 heap queue에 포함되는 것을 알 수 있다. 다익스트라 알고리즘을 위한 첫 heap queue부터 경로 정보를 포함시키는 것이다.

for cost, j in graph[st]:
        if prev_cost + cost <= vis[j]:
            vis[j] = prev_cost + cost
            new_his = [h for h in history]
            new_his.append(j)
            hq.heappush(qu, [prev_cost + cost, j, new_his]) # [비용, 도착지, 경로]

 

이후에는 st라는 노드에서 갈 수 있는(=for cost, j in graph[st]:) 후보를 heap에 넣을 때 new_his에 현재 경로를 추가함으로써 heap queue에 경로 정보를 추가할 수 있다.

 

한계점

이렇게 경로를 추가하는 방식은 여러 최단 거리 경로가 있을 때, 그 중 한 가지 경로만 알 수 있다는 한계가 있다.