백준 1753번 최단경로 파이썬

리뷰

다익스트라를 활용한 문제 풀이

 

문제 풀이

1. 노드의 개수 n와 간선의 개수 m를 받아오고 시작점 k을 받아온다.
2. 각 노드의 간선 정보를 edge 리스트에 초기화 해준다. 인덱스 참조를 위해 n + 1 개의 빈 리스트를 2중 리스트로 생성
3. 각 노드까지의 거리를 나타낼 dist 리스트를 초기화 해준다. 마찬가지로 n + 1 개의 INF값으로 생성해 준다.
4. m개의 간선 정보를 받아온다, 각 노드 시작점에 [거리, 노드] 형식의 리스트를 추가해 준다.
5. 시작점이 될 힙을 거리 0, 시작노드 k로 초기화 해주고, 시작 위치의 거리를 0으로 변경해 준다.
6. 힙이 존재할때 까지 while루프를 돌아 최소 힙을 pop해주고 현재 거리와 노드를 뽑아내 준다.
7. 만약 현재 거리가 dist에 저장된 현재 노드의 거리와 다를 경우 continue 처리해 준다.
8. 다음 노드가 가지고 있는 간선을 탐색한다. 다다음 노드로 이동할 거리는 nw, 다다음 노드는 nv이다.
9. 다다음 노드까지의 거리가 현재까지의 거리보다 작을 경우 현재까지의 거리를 다다음 노드까지의 거리로 바꿔준다.
10. 해당 노드의 거리와 노드 정보를 힙에 추가해 준다.
11. while문 종료 후 최단 거리가 아직 INF일 경우 가지 못하는 경로이기에 INF로 출력, 아닐 경우 최단거리 출력

 

참고 사항

다익스트라 진행 방식은 그냥 수학 공식처럼 외워야 할 것 같다.

 

 

정답 코드

import sys
import heapq

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
edge = [[] for _ in range(n + 1)]
dist = [INF] * (n + 1)
for _ in range(m):
    u, v, w = list(map(int, sys.stdin.readline().split()))
    edge[u].append([w, v])
heap = [[0, k]]
dist[k] = 0
while heap:
    cw, cv = heapq.heappop(heap)
    if dist[cv] != cw: continue
    for nw, nv in edge[cv]:
        if dist[nv] > cw + nw:
            dist[nv] = cw + nw
            heapq.heappush(heap, [dist[nv], nv])
for i in range(1, n + 1):
    print("INF" if dist[i] == INF else dist[i])