최단경로 - 1753

1. 개요

문제 링크: https://www.acmicpc.net/problem/1753

2. 코드

import sys
import heapq
input = sys.stdin.readline

# # of vertexes: n, # of edges: m, starting node: k
n, m = map(int, input().split())
k = int(input())
INF = int(1e9)

# initialize
graph = [[] * (n+1) for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            dest = i[0]
            adj_dist = i[1]

            cost = dist + adj_dist
            if cost < distance[dest]:
                distance[dest] = cost
                heapq.heappush(q, (cost, dest))

dijkstra(k)
for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

3. 풀이 메모

1. 최소힙을 사용하자.
   학교에서 배울 때는 지나가듯 언급됐으나, 최소힙은 더 이상 생소한 개념이 아닐 뿐더러, 단순 루프로 문제를 해결할 경우 O(V^2)의 시간복잡도로 문제가 해결된다는 단점이 있다. 최소힙을 사용한다면 시간 복잡도를 O(ElogV)로 줄일 수 있다.

   • 루프로 문제 해결: graph 배열 내부에 있는 모든 간선 정보를 다 한번씩 살펴봄. 이 과정에서 '최소 거리' 가 가장 짧은 간선을 타야 하는데, 선형 검색으로 추가 루프가 필요.
   • 최소힙으로 문제 해결: 애초부터 짧은 간선 거리부터 처리되도록 해 추가 루프를 삭제. 시간복잡도는 오로지 최소힙의 데이터 추가/삭제 시간과 연관됨.

2. 시간복잡도 문제
   최소힙의 데이터 삭제는 O(logN)의 시간 복잡도를 가진다. 이 과정은 순전히 최상위 노드를 트리에서 삭제하고, 최하위 노드를 상위로 올린 뒤 제자리까지 도달할 때까지 swap하는데 걸리는 시간이라고도 볼 수 있다. 최소힙에 들어가는 요소는 간선에 대한 정보이며, 모든 간선 정보가 한번씩 탐색이 되므로 O(E logE)라 볼 수 있다. 이때, fully connected graph 를 고려하면 항상 간선의 개수는 많아봐야 V(V-1)이라는 사실을 알 수 있다. 따라서 E ~ V^2라 볼 수 있으며, 최종적으로 시간복잡도는 O(E logV^2) = O(E 2logV) = O(E * logV) 라 결론 내릴 수 있다.

3. 파이썬과 우선순위 힙
   파이썬의 우선순위 힙은 heapq 라이브러리를 통해서 사용할 수 있으며, 일반 list를 힙으로 만드는 방식으로 정의한다. 만약 리스트나 튜플을 요소로 사용한다면, 가장 첫번째 요소값을 기준으로 최소힙을 구성해준다.

   heapq.heappush(q, (0, start))

4. 코멘트

유명한 다익스트라 알고리즘이다. 사실상 구현 문제지만, 머리 속에서 익숙하게 받아들이는 것은 별개이니 유사 문제를 계속 풀어보는게 좋을 것 같다.