[Python]동적계획법과 최단거리 역추적 백준 11779

   문제

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

다익스트라 알고리즘을 이용해 최소비용을 구하는문제에서 경로를 출력하는것이 추가

되었다.최소힙을 통해 다익스트라를 구현하였으며 result 배열에 이전에는 최소비용만 

저장하였다면 이번에는 그경로까지 저장하였다.

result에 모든 경로를 저장 하는방법과 

이전 노드들을 저장하여 역추적하는 방법이 있다.

이번에 역시 두가지 방법 모두 구현해보았다.

import sys
import heapq
 
n=int(sys.stdin.readline())#정점개수
m=int(sys.stdin.readline())#간선개수
 
G=[[] for _ in range(n+1)]
 
INF=sys.maxsize
result=[[INF,""] for _ in range(n+1)]
 
for _ in range(m):
    s,e,d=map(int,sys.stdin.readline().split())
    G[s].append([d,e])
 
S,E=map(int,sys.stdin.readline().split())#출발,도착
result[S][0]=0
result[S][1]=str(S)
 
##############################최소힙을 통한 다익스트라 구현
q=[]
heapq.heappush(q,[0,S])
while q:
    dis,end=heapq.heappop(q)
 
    if result[end][0]<dis:#해당경로가 이전 경로보다 길다면 연결된 노드에대해 탐색할 필요가없다.
        continue
 
 
    for d,x in G[end]:
        d+=dis
        if result[x][0]>d:
            result[x][0]=d
            result[x][1]=result[end][1]+","+str(x)#,로 구분하여주었다.
            heapq.heappush(q,[d,x])
 
 
print(result[E][0])
trace=result[E][1].split(",")
print(len(trace))
print(*trace)

첫번째 방법에서는 

result[x][1]=result[end][1]+","+str(x)

이부분을

result[x][1]=result[end][1]+str(x)

구현하여 출력해서 한참고생했다.

노드가 두자리가 되면 출력시 두개로 나누어져서 제대로 출력할수 없다. 사이사이

마다 ","를 넣어주어서 구분하고 출력해주었다.

두번째 방법은 이전에 방문했던 도시를 저장하여 역추적 하는방법이다.

import sys
import heapq
 
n=int(sys.stdin.readline())#정점개수
m=int(sys.stdin.readline())#간선개수
 
G=[[] for _ in range(n+1)]
 
INF=sys.maxsize
result=[INF for _ in range(n+1)]
Trace=[0 for _ in range(n+1)]
 
for _ in range(m):
    s,e,d=map(int,sys.stdin.readline().split())
    G[s].append([d,e])
 
S,E=map(int,sys.stdin.readline().split())
result[S]=0
 
 
 
q=[]
heapq.heappush(q,[0,S])
while q:
    dis,end=heapq.heappop(q)
 
    if result[end]<dis:#해당경로가 이전 경로보다 길다면 연결된 노드에대해 탐색할 필요가없다.
        continue
 
 
    for d,x in G[end]:
        d+=dis
        if result[x]>d:
            result[x]=d
            Trace[x]=end#이전값 저장
            heapq.heappush(q,[d,x])
 
print(result[E])
 
 
#역추적
count=0
path=[E]
tmp=Trace[E]
while tmp!=0:
    path.append(tmp)
    tmp = Trace[tmp]
 
 
print(len(path))
print(*path[::-1])