[백준] 1753번 최단경로(다익스트라 알고리즘)(Python - 파이썬)

백준 1753번 문제입니다. (solved.ac)기준 골드 5 문제입니다.

문제 접근

시작점이 주어졌기 때문에 다익스트라 알고리즘을 이용하여 간단하게 최단 경로를 구할 수 있는 문제입니다.

그래프의 노드를 가리키는 정점(V)의 개수의 범위가 20,000 이하이기 때문에 시간복잡도가 O(V^2)인 간단한 다익스트라 알고리즘으로는 시간초과 오류가 발생할 것입니다(V는 노드의 개수).

따라서 우선순위 큐를 사용하여 개선된 다익스트라 알고리즘으로 문제를 해결하였습니다.

개선된 다익스트라 알고리즘은 최악의 경우에도 시간 복잡도가 O(ElogV)로 보장됩니다(V는 노드의 개수, E는 간선의 개수).

개선된 다익스트라 알고리즘은

1. 출발 노드(start)를 설정

2. 최단 거리 테이블(distance)을 int(1e9)로 설정(노드 수 만큼)

3. 우선순위 큐를 사용하여 방문처리없이 최단거리(distance)가 가장 짧은 노드가 추출됨(이미 처리한 노드라면 무시)

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 전체 노드를 처리할 때까지 3, 4번을 반복

 

정답 코드

import heapq
import sys

INF = int(1e9)

# 정점의 개수(v), 간선의 개수(e)
v, e = map(int, sys.stdin.readline().split())

# 시작 정점의 번호(start)
start = int(input())

graph = [[] for _ in range(v + 1)]

distance = [INF] * (v + 1)

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

# 우선순위 큐를 이용한 개선된 다익스트라 알고리즘 
# 시간 복잡도 : O(mlogn)
def dijkstra(start):
   
    q = []
    # 우선순위 큐를 사용
    heapq.heappush(q, (0, start))
    # 시작 노드에서의 최소 거리는 0
    distance[start] = 0

    # 큐가 빌 때까지 반복
    while q:

        dis, now = heapq.heappop(q)
		
        # 해당 노드를 이미 처리한적이 있다면 무시
        if distance[now] < dis:
            continue

        for i in graph[now]:
            cost = dis + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

for i in range(1, v + 1):

    # 경로가 존재하지 않는 경우에는 INF출력
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])