[백준] 1753. 최단경로/Python - 골드4

❓문제

성능 요약

메모리: 136204 KB, 시간: 380 ms

분류

다익스트라, 그래프 이론, 최단 경로

 

문제 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

✍🏻풀이

최단 경로를 구하기 위해 인접행렬과 인접리스트를 사용할 수 있지만 인접 행렬을 사용하는 경우, 시간 복잡도가 O(V²)이 됩니다. 그러나 인접 리스트를 사용하는 경우 시간 복잡도가 O(E * logV)이 되므로 인접 리스트를 사용해서 풀겠습니다. 그리고 다익스트라는 Heap을 사용하는 것이 빠릅니다.

heapq를 사용하기 위해 pq를 생성해 (가중치, 시작 정점) 쌍으로 힙큐에 넣어준다. 그리고 dist는 각 정점의 최단 거리 테이블을 나타낸다. 시작 노드에서의 최단 거리는 0이므로 dist[K] = 0으로 초기화한다.

힙큐가 비어있을 때까지 다음 과정을 반복한다.

힙큐에서 현재 거리와 현재 정점 위치를 꺼낸다. 그리고 현재 정점의 인접 리스트에서 최단 거리를 찾는다. 최단 거리를 찾았다면 현재 거리와 정점을 힙큐에 넣는다.

마지막으로 dist를 출력하여 각 정점에서의 최단 거리를 출력하면 된다.

💻코드

import sys
import heapq

input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())
adjlist = [[] for _ in range(V+1)]

for i in range(E):
    u, v, w = map(int, input().split())
    adjlist[u].append((v, w))

pq = []
heapq.heappush(pq, (0, K))
dist = [1e9] * (V+1)
dist[K] = 0

while pq:
    d, cur = heapq.heappop(pq)

    for v, w in adjlist[cur]:
        if dist[v] > dist[cur] + w:
            dist[v] = dist[cur] + w
            heapq.heappush(pq, (dist[v], v))

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

📍후기

그래프하면 기본적으로 DFS, BFS만 생각하는데 다익스트라 알고리즘도 중요한 것 같다.