[그래프] 백준 #1753 최단경로 - Python

🗂️ 문제

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

 

💡 접근법

가중치가 자연수인 방향 그래프이므로 최단 경로를 구하기 위해 다익스트라를 사용해야 한다. 또한 거리가 가장 작은 노드를 자동으로 선택하기 위해 우선순위 큐(heapq)를 사용한다.

 

distance의 요소는 모두 INF로 초기화되어 있다. 만약 if distance[now_node] < dist: 조건을 만족할 경우 now_node는 이미 방문된 노드이므로 방문 처리를 위한 visited 리스트가 따로 필요하지 않다.

또한 해당 조건을 만족할 경우 이미 dist는 distance[now_node]보다 큰 값이기 때문에 dist 값으로는 now_node와 연결된 다른 노드의 최단 거리를 구할 수 없다. 따라서 continue를 통해 스킵한다.

 

최단 거리를 구하고 만약 최단 거리 리스트(distance)의 값보다 작다면 distance에 값을 업데이트하고 heapq에 (거리, 노드)를 삽입한다.

 

👀 배운 코드

import sys
import heapq

INF = int(1e9)

V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())

graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
distance = [INF] * (V+1)

for _ in range(E):
    n, e, w = map(int, sys.stdin.readline().split())
    graph[n].append((e, w))

def dijkstra(K):
    queue = []
    heapq.heappush(queue, (0, K))  # (거리, 시작노드)로 초기화, 최소힙
    distance[K] = 0
    while queue:
        dist, now_node = heapq.heappop(queue)

        if distance[now_node] < dist:  # 큐에서 꺼낸 최단 거리가 최단거리 리스트에 기록된 거리보다 크면, dist는 최단거리 정보가 아니다. 따라서 굳이 비교할 필요가 없다.
            continue
        
        for e, w in graph[now_node]:
            cost = dist + w  # 최단 거리 계산
            if cost < distance[e]:  # 최단 거리로 업데이트
                distance[e] = cost
                heapq.heappush(queue, (cost, e))

dijkstra(K)

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

 

🧐 배운 점

• 가중치가 자연수인 방향 그래프이고, 다른 모든 노드로의 최단 경로를 구해야 할 경우 다익스트라를 사용한다.
• 무한대에 가까운 값은 int(1e9)로 나타낸다.

 

✅ 정답 확인