[백준 / Python] 1753 최단경로 (다익스트라)

결과

• 메모리: 167436 KB
• 시간: 868 ms

알게된 것

• 다익스트라: 한 정점에서 다른 모든 정점으로의 최단 거리

• 플로이드-와샬: 모든 정점에서 다른 모든 정점으로의 최단 거리

• heap (https://hocheon.tistory.com/70) (https://dingrr.com/blog/post/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-heap%ED%9E%99)

  1. 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 형태의 자료구조. O(log n)
  2. 삽입: 트리 마지막 원소에 추가
  3. 삭제: 루트 노드 제거, 마지막 노드를 루트로 이동
  4. 이진 탐색트리와의 차이점: 이진 탐색트리는 탐색을 위함, 힙은 최소/최대값 찾기 위함.
  5. 왜 사용?: 데이터를 큐나, 배열에 데이터를 넣고 최대값이나 최소값을 찾으려면 최악의 경우 일일히 하나씩 데이터를 검사해야 하기때문에 O(n)의 시간복잡도를 가집니다. 하지만, 힙을 사용하면 O(log n)으로 시간복잡도가 현격하게 줄어듭니다.
  6. 코딩 테스트 문제 중 최솟값 , 혹은 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간측면에서 굉장히 효율적인 구현이 가능하다.
  7. 핵심: 최대/최소값 구하기 위한 자료구조, O(log n), 완전이진트리

• heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있다.

• 이진트리: 노드가 왼쪽자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다. 이때 각 노드의 자식은 2명 이하만 유지해야한다.

• 완전 이진트리: 루트부터 노드가 채워져있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져있는 이진트리를 완전이진트리(complete binary tree)라고 한다.

• 참고 블로그: https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

• sys.stdin.readline이 안먹혀서 주피터에서는 그냥 input 사용해야 한다.

문제 해결 방법

• 다익스트라는 처음 풀어서 블로그 보고! https://developmentdiary.tistory.com/391 🔥👍
• 위 블로그에서 heapq를 제대로 이해하지 못해서 가독성 편의를 위해 append([v, w]) 로 바꿨더니 오류가 남. # 거리를 앞에두어 우선순위 큐에 넣을때 거리가 비교되도록한다. 주목! => heapq 다시 한 번 개념 복습하기
• heapq 모듈 특성상, pop하게 되면 가장 작은 값을 가진 원소가 리턴되기 때문에 힙에 원소를 저장할 때 '경로값, 노드' 순으로 넣어야 한다. 경로값을 기준으로 최단 경로를 찾아 나가야 하는 로직이기 때문. 참고 블로그 (whwl.tistory.com/33)

제출 코드

import sys
import heapq

# ip = input # 주피터에서는 readline 안먹혀서 input 써야 함.
ip = sys.stdin.readline # 제출할 때만 주석 해제. 시간이 단축되므로. (1200ms to 868ms)

INF = sys.maxsize
V, E = map(int, ip().split())

G = [[] for _ in range(V + 1)]
K = int(ip())

for _ in range(E):
    u, v, w = map(int, ip().split())
    G[u].append([w, v])

result = [INF for _ in range(V + 1)]
result[K] = 0

q = []
heapq.heappush(q, [0, K]) # 거리를 앞에두어 우선순위 큐에 넣을때 거리가 비교되도록한다.

while q:
    dist, to = heapq.heappop(q)

    if result[to] < dist: # 해당 경로가 이전경로보다 길다면 연결된 노드에 대해 탐색할필요가없다.
        continue
    for d, t in G[to]: # 연결된 노드 탐색
        d += dist # 이전거리와 현재 연결된 노드의 거리를 더해서
        if d < result[t]: # 거리비교 # 거리가 이전보다 짧으면
            result[t] = d # 거리를 갱신시키고
            heapq.heappush(q, [d, t]) # 우선순위 큐에 넣어준다.

for i in range(1, V + 1):
    print(result[i] if result[i] != INF else "INF")