백준 11779번 최소비용 구하기 2 파이썬 다익스트라

리뷰

오랜만의 파이썬 풀이였는데 C++을 주로 쓰다보니 이제 파이썬이 익숙치 않아 큰일이다..

 

문제 풀이

1. 일반적인 다익스트라 풀이로 쭉 진행한다.
2. 인접리스트를 n + 1크기로 초기화 후 단방향으로 값을 받아준다.
3. 거리 리스트를 적당히 큰 값으로 설정하고 n + 1 크기로 초기화 해준다.
4. 경로를 나타낼 path 배열을 0 값으로 n + 1크기로 초기화 해준다.
5. 시작 위치의 거리를 0으로, 힙을 세팅해 주고 while문을 돌려준다.
6. 힙에서 pop한 현재 노드를 기준으로 인접리스트를 돌고 만약 현재 까지 구한 해당 노드까지의 거리보다 현재 거리가 더 작을경우 갱신해 준다.
7. 이때 path 배열의 다음 노드 인덱스에 현재 노드를 넣어준다. 이후 갱신한 거리와 다음 노드를 힙에 추가해준다.
8. while 루프가 끝난 후 우선 목적지 까지의 최단 거리를 출력해 준다.
9. ans 리스트를 목적 노드를 넣고, 목적 노드에서 시작 노드까지 path리스트를 통해 역추적을 시작해 준다.
10. 역추적이 완료되면 리스트를 뒤집은 뒤 ans 리스트의 길이와 ans 리스트의 요소를 출력해 준다.

 

참고 사항

출발 도시와 도착 도시도 포함하므로 ans 리스트를 초기화 할때 목적지 노드를 넣어주었다.

방문하는 도시 순서대로 출력해야 하므로 마지막에 ans 배열을 뒤집어 주었다.

 

 

정답 코드

import sys
import heapq

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
lst = [[] for _ in range(n + 1)]
dist = [999999999] * (n + 1)
path = [0] * (n + 1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    lst[a].append([c, b])
sx, dx = map(int, sys.stdin.readline().split())
heap = [[0, sx]]
dist[sx] = 0
while heap:
    cd, cn = heapq.heappop(heap)
    if dist[cn] != cd: continue
    for i in lst[cn]:
        nd, nn = i
        if dist[nn] > cd + nd:
            dist[nn] = cd + nd
            path[nn] = cn
            heapq.heappush(heap, [dist[nn], nn])
print(dist[dx])
ans = [dx]
while sx != dx:
    dx = path[dx]
    ans.append(dx)
ans.reverse()
print(len(ans))
print(*ans)