이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프는 인접 리스트로 구현하였다. 기존의 다익스트라 알고리즘 문제와 조금 다른 점이 있다면 방문한 노드들을 같이 출력해야 한다는 것이었다. 방문한 노드를 담는 리스트를 전역 변수로 선언하게 되면 방문하여 탐색만 했던 모든 노드를 모두 담게 되기 때문에 이 방법은 옳지 않았다. 그래서 생각하던 중 각 노드까지의 최소 거리를 담는 리스트에 경로까지 담아보기로 하였다. dist['최단 거리', '방문한 노드의 수', '방문한 노드 리스트']의 형태로 저장하였고, 다익스트라 알고리즘 내에서 최단 거리의 조건에 만족할 경우 방문한 노드의 수를 1 증가시키고, 방문한 노드 리스트에 다음으로 갈 노드를 넣어주었다. 이 방식으로 구현하면 dist[end]에 최단거리, 방문한 노드의 수, 방문 경로가 담기게 된다.

• n을 입력받는다.
• m을 입력받는다.
• graph를 2차원 리스트로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a]에 (b, c)를 넣는다.
• start, end를 입력받는다.
• INF에 sys.maxsize를 저장한다.
• dist리스트를 선언하고 [INF, 0, []] n+1개를 채운다.
• dist[start][0]을 0으로 갱신한다.
• dist[start][1]을 1 증가시킨다.
• dist[start][2]에 start를 넣는다.
• 다익스트라에 사용할 큐 q를 최소힙으로 선언하고 (0, start, 1)을 넣는다. (0: 현재까지의 거리, start: 현재 노드, 1: 현재까지 방문한 노드의 수)
• q가 존재할 동안 반복하는 while문을 돌린다.
  -> distance, cur, cnt를 q에서 추출한다.
  -> 만약 distance가 dist[cur][0]보다 클 경우 다음 반복을 넘어간다.
  -> graph[cur]을 순회하는 nxt, dst에 대한 for문을 돌린다.
  --> cost에 distance+dst를 저장한다.
  --> 만약 dist[nxt][0]이 cost보다 클 경우,
  ---> dist[nxt][0]을 cost로 갱신한다.
  ---> dist[nxt][1]을 cnt+1로 갱신한다.
  ---> dist[nxt][2]를 dist[cur][2]+[nxt]로 갱신한다.
  ---> q에 (cost, nxt, cnt+1)을 넣는다.
• dist[end][0]을 출력한다.
• dist[end][1]을 출력한다.
• dist[end][2]를 언패킹하여 출력한다.

Code

import heapq
import sys
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())
INF=sys.maxsize
dist=[[INF, 0, []] for _ in range(n+1)]
dist[start][0]=0
dist[start][1]+=1
dist[start][2].append(start)
q=[]
heapq.heappush(q, (0, start, 1))
while q:
    distance, cur, cnt=heapq.heappop(q)
    if distance>dist[cur][0]:
        continue
    for nxt, dst in graph[cur]:
        cost=distance+dst
        if dist[nxt][0]>cost:
            dist[nxt][0]=cost
            dist[nxt][1]=cnt+1
            dist[nxt][2]=dist[cur][2]+[nxt]
            heapq.heappush(q, (cost, nxt, cnt+1))
print(dist[end][0])
print(dist[end][1])
print(*dist[end][2])