[백준 으깨기] 1753 - 최단경로 (with. 다익스트라/Dijkstra)

문제 정보

1753 - 최단경로

1753번: 최단경로

---

문제 쪼개기

문맥 파악하기

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

입력 조건 확인하기

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 20,000)와 간선의 개수 E(1 ≤ E ≤ 300,000)가 주어진다. 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력 조건 확인하기

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

들어가기

이 문제는 다익스트라 알고리즘을 이용하는 대표적 문제로, 문제 풀이보단 다익스트라에 대해 설명하고자 한다.

다익스트라 알고리즘(Dijkstra algorithm)은 그래프에서 정점(Vertex)들 간의 최단 경로를 찾는 대표적인 알고리즘이다. 벨만-포드 알고리즘(Bellman-Ford algorithm)과 달리, 다익스트라 알고리즘은 간선의 가중치(Weight)가 음이 아닌 경우에 하나의 출발점에 대한 각 정점까지의 최단 경로를 찾을 수 있다.

---

그래프의 각 정점들은 출발점으로부터의 최단 경로 가중치(d)를 가지는데, 각 정점을 방문하면서 인접 정점들의 최종 최단 경로 가중치를 갱신해간다. 이때, 정점은 한번만 방문하고, 방문한 정점의 최단 경로 가중치는 확정됐다고 할 수 있다. 단, 방문 순서는 최단 경로 가중치가 가장 작은 정점을 먼저 방문해야 하기 때문에 가중치를 키(key)값으로 하는 우선 순위 큐를 이용한다. 이런 특징으로 다익스트라 알고리즘은 가장 작은 가중치를 우선 방문하는 탐욕(Greedy) 알고리즘의 일종이라고 할 수 있다.

---

위 그림은 문제의 예제 입력 1을 시각화한 그래프이다. 최단 경로 가중치는 INF로, 아직 값이 정해지지 않음을 의미한다. 출발점은 1번 정점이기 때문에 1번 정점에 대한 최단 경로 가중치를 확정하고, 인접 정점에 대해 최단 경로 가중치를 갱신한다.

1번 정점 방문

1번 정점에서 1번 정점까지 최단 경로 가중치는 0이다. 인접 정점들의 최단 경로 가중치를 갱신하는데, 이 값은 '현재 정점의 최단 경로 가중치와 간선의 가중치의 합'과 '인접 정점의 현재 최단 경로 가중치' 중 최솟값이 된다.

2번 정점 방문

이후, 가장 작은 최단 경로 가중치 d = 2인 2번 정점을 방문하고, 이를 반복한다.

3번 정점 방문

d = 3인 3번 정점을 방문하고, 이를 반복한다.

4번 정점 방문

d = 7인 4번 정점을 방문하고, 이를 반복한다. 5번 정점의 경우, 접근할 수 있는 간선이 없기 때문에 방문이 불가하다.

 

---

문제 으깨기

제출 코드

from sys import stdin
import heapq

UPPER_WEIGHT = 300000*10 + 1

class Node:
    def __init__(self, n: int):
        self.n = n
        self.edges = []
        self.is_visited = False
        
    def add_edges(self, w: int, node_idx: int):
        self.edges.append((w, node_idx))
        

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

nodes = [Node(n) for n in range(V + 1)]
smallest_weights = [UPPER_WEIGHT for _ in range(V + 1)]

start_node_idx = int(stdin.readline())

for _ in range(E):
    u, v, w = map(int, stdin.readline().split())
    nodes[u].add_edges(w, v)
    
pr_qu = []
heapq.heappush(pr_qu, (0, start_node_idx))
smallest_weights[start_node_idx] = 0
while pr_qu:
    cur_w, cur_node_idx = heapq.heappop(pr_qu)
    if nodes[cur_node_idx].is_visited:
        continue
    
    nodes[cur_node_idx].is_visited = True
    for edge in nodes[cur_node_idx].edges:
        next_w, next_node_idx = edge[0] + cur_w, edge[1]
        if next_w < smallest_weights[next_node_idx]:
            smallest_weights[next_node_idx] = next_w
            heapq.heappush(pr_qu, (next_w, next_node_idx))

for i in range(1, len(smallest_weights)):
    if smallest_weights[i] == UPPER_WEIGHT:
        print('INF')
    else:
        print(smallest_weights[i])

 

---

제출 결과

메모리: 71600 KB, 시간: 892 ms