[백준] 최단경로(골드4)

문제 링크

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

 

힙큐

힙큐는 우선순위 큐라고도 하는데, 제일 작은 수를 제일 먼저 pop 할 수 있도록 해주는 큐이다. 

그래서 항상 pop을 하면 제일 작은 수가 먼저 pop이 되기 때문에 greedy 탐욕적이라고 불리기도 한다. 

 

다익스트라 알고리즘 이용 문제

 

우선 이 문제에서 사용하는 그래프는 단방향 그래프이기 때문에 

V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

그래프는 이런식으로 코드를 구현하였다.

 

weights = [float('inf')] * (V + 1)
weights[K] = 0
wq = [(0, K)]

다음은 시작점인 K를 기준으로 각 노드까지의 최단 거리를 담은 weights 배열을 생성하였다. 

 

힙큐를 돌면서 

 

이미 더 좋은 경로를 찾았을 경우 

if weights[cnt_node] < cnt_weight:
    continue

를 통해 효율적으로 코드를 구현할 수 있다.

 

for neighbor, weight in graph[cnt_node]:
    weight = cnt_weight + weight

    if weight < weights[neighbor]:
        weights[neighbor] = weight
        heapq.heappush(wq, (weight, neighbor))

 

for neighbor, weight in graph[cnt_node]:
    weight = cnt_weight + weight

    if weight < weights[neighbor]:
        weights[neighbor] = weight
        heapq.heappush(wq, (weight, neighbor))

 

연결 노드들을 탐색하며 끝까지 돈다

 

for i in range(1, V + 1):
    if weights[i] == float('inf'):
        print('INF')
    else:
        print(weights[i])

 

결과를 출력한다

 

전체 코드

import sys
import heapq

input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

weights = [float('inf')] * (V + 1)
weights[K] = 0
wq = [(0, K)]

while wq:
    cnt_weight, cnt_node = heapq.heappop(wq)

    if weights[cnt_node] < cnt_weight:
        continue

    for neighbor, weight in graph[cnt_node]:
        weight = cnt_weight + weight

        if weight < weights[neighbor]:
            weights[neighbor] = weight
            heapq.heappush(wq, (weight, neighbor))

for i in range(1, V + 1):
    if weights[i] == float('inf'):
        print('INF')
    else:
        print(weights[i])