최소비용 구하기 2


다익스트라 알고리즘

다익스트라 알고리즘을 이용하는 문제이다. 다익스트라 알고리즘에 대한 포스팅은 아래의 두 문제에서 해놓았다.

‘최소비용 구하기 2’는 기본적인 다익스트라 알고리즘 문제에 경로 찾기가 추가된 형태이다.


먼저 다익스트라 알고리즘에 대해서 간략하게 집고 넘어가보자.

  • 초기에 각 점의 시작점으로 부터의 최단거리는 inf이다.
  • 시작점으로부터 뻗어나가는 간선을 탐색한다. 간선의 가중치 만큼 도착지에 업데이트 해준다.
  • 아직 방문하지 않은 점들 중 최단거리가 최소인 점을 방문한다.
  • 해당 점(a)으로 부터 뻗어나가는 간선을 탐색한다. 점’a’의 시작점으로부터 최단거리 + 간선의 가중치가 기존에 저장되어있던 최단거리보다 작을 때, 해당 노드의 최단거리를 업데이트한다.
  • 이 과정을 모든 노드를 방문할 때 까지 반복하면, 모든 노드에 대해 시작점으로 부터 최단거리를 구할 수 있다.(단, 음의 가중치를 가지는 간선이 존재할 경우에는 사용할 수 없다.)


경로

시작점으로 부터 최단거리와 함께, 최소 비용을 갖는 경로에 포함되어 있는 도시의 정보도 찾아내야 한다.

이를 위해 ‘way’리스트를 만들었다. 음의 값을 가지는 노드는 존재하지 않음으로, 초기 값은 모두 -1로 저장해 두었다. 최단 경로를 탐색해 나가면서, ‘way’ 리스트에 최소 비용을 갖는 경로로 이동할 때, 해당 노드를 방문하기 이전 노드를 저장했다.

while point:
    w_a, a = hq.heappop(point)
    if a == end:
        print(dp[a])
        break
    if a in bridge:
        for x, w_x in bridge[a]:
            if dp[x] > w_a + w_x:
                #x의 최단거리 업데이트
                dp[x] = w_a + w_x
                #이전 노드 저장
                way[x] = a
                #heapq에 노드 추가
                hq.heappush(point,[dp[x], x])


1 -> 3 -> 5 로 이동한 경우, way[5] = 3, way[3] = 1, way[1] = -1 이다. 이 정보를 사용해 5까지 어떻게 이동해 왔는지 역추적할 수 있다.

#경로 복원
memo_way=[]
while True:
    memo_way.append(a+1)
    a=way[a]
    if a ==-1:
        break


CODE

import sys
import heapq as hq
read=sys.stdin.readline
inf = sys.maxsize

n=int(read())
m=int(read())

bridge=dict()
for _ in range(m):
    a,b,c=map(int,read().split())
    a,b=a-1,b-1
    if a not in bridge:
        bridge[a]=[]
    bridge[a].append((b,c))

start,end=map(int,read().split())
start,end=start-1,end-1
#이전 노드 저장
way=list(-1 for _ in range(n))
#start로부터 최단거리 저장
dp=list(inf for _ in range(n))
dp[start]=0

point=[[0, start]]
#heapq를 사용해 아직 방문하지 않은 점들 중 최단거리의 점 탐색
hq.heapify(point)

while point:
    w_a, a = hq.heappop(point)
    if a == end:
        print(dp[a])
        break
    if a in bridge:
        for x, w_x in bridge[a]:
            if dp[x] > w_a + w_x:
                #x의 최단거리 업데이트
                dp[x] = w_a + w_x
                #이전 노드 저장
                way[x] = a
                #heapq에 노드 추가
                hq.heappush(point,[dp[x], x])

#경로 복원
memo_way=[]
while True:
    memo_way.append(a+1)
    a=way[a]
    if a ==-1:
        break

print(len(memo_way))
print(*memo_way[::-1])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]