[백준/Python] 1753번: 최단 경로

문제

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

1753번: 최단경로

---

문제 요약

간선의 정보를 입력 받아 방향 그래프가 주어진다.

+ 모든 정점에는 1부터 정점 개수만큼의 번호가 매겨진다.

 

간선의 개수만큼 세 개의 정수 (u, v, w)가 순서대로 주어진다.

+ u에서 v로 가는 가중치 w인 간선이 존재한다는 의미이다.

 

시작점 번호를 입력 받고, 시작점에서 다른 모든 정점으로의 최단 경로를 출력한다.

 

+ 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다.

---

코드

from collections import deque
import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    q = []
    
    # start 노드로 가기 위한 최단 거리는 0으로 설정하여 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 (첫번째 인자부터 대소 비교)
        # dist는 이전 노드에서 now 노드로 가기 위한 최단 거리
        dist, now = heapq.heappop(q)
        
        # 이전에 설정된 start노드에서 now 노드까지 최단 거리가 더 짧다면 무시
        if distance[now] < dist:
            continue
        
        # now 노드와 연결된 다른 인접한 노드(i[0] 노드)들 확인
        for i in graph[now]:
            cost = dist + i[1]
            
            # start 노드 -> now 노드 -> i[0] 노드 거리 < 이전까지 설정된 start -> i[0] 노드 거리
            if cost < distance[i[0]]:
                distance[i[0]] = cost # start 노드 -> i[0] 노드 최단 거리 갱신
                heapq.heappush(q, (cost, i[0]))   

n, m = map(int, input().split())
# n은 정점 개수, m은 간선 개수

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

INF = int(1e9) # INF = 무한

graph = [[] * (n + 1) for _ in range(n + 1)] # 그래프 초기화

distance = [INF] * (n + 1) 
# 시작 노드에서 i까지의 최단 거리를 저장하는 배열 (초기: 무한)

# 간선 정보 입력
for _ in range(m):
    u, v, w = map(int, input().split())
    # u -> v 의 비용 w
    graph[u].append((v, w))

# 다익스트라 알고리즘 수행
dijkstra(k)

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

---

코드 설명

1. 간선의 정보(u, v, w)를 입력 받고 배열 graph의 u번째 인덱스에 (v, w)를 저장한다.

+ v는 u에 인접한 노드의 인덱스, w는 u 노드에서 v 노드까지의 거리(가중치)이다.

 

2. 시작점에서 i까지의 최단 거리를 저장하는 배열 distance를 생성한다.

 

3.. 다익스트라 알고리즘을 수행한다.

 

3 - 1. (0, 시작점 번호)를 최소힙에 삽입한다. (0: 시작점 -> 시작점)

+ 힙에 배열이 삽입된 경우, 첫번째 인덱스부터 대소를 비교하여 최소힙을 구성한다.

 

3 - 2. distance[시작점 번호]를 0으로 설정한다.

 

3 - 3. 힙이 비워질 때까지 힙에서 한 쌍의 노드 정보를 꺼낸다.

+ 노드 정보: 시작 노드에서 현재 노드 now까지의 거리 dist

+ 인접한 정점 중 dist가 가장 짧은 점부터 방문한다. (최소 힙이므로)

 

3 - 4. dist가 distance[now]보다 크다면 더 볼 필요 없이 최단 거리가 아니므로 continue한다.

+ 이미 방문한 노드이다.

 

3 - 5. dist +  i[1] (현재 노드 now와 인접한 노드 i[0]까지의 거리)가 이전까지 갱신된 distance[i[0]]보다 짧다면, distance[i[0]] (시작점부터 i[0] 노드까지의 최단 거리, cost)를 갱신하고 힙에 (cost, i[0])를 삽입한다.

 

4. 형식에 맞게 distance 내용을 출력한다.