최단 경로

출처 : 백준 #1753

시간 제한	메모리 제한
1초	256MB

---

문제

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

---

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 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를 출력하면 된다.

---

입출력 예시

예제 입력 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1

0
2
3
7
INF

---

풀이

생각

• 직전에 풀었던 문제인 특정거리의 도시 찾기 문제와 매우 유사하다.
• 그래프에서 최단 거리를 구하는 문제이다.
• 최단 거리를 구하는 알고리즘은 다익스트라, 플로이드 워셜 등이 있다.
• 범위가 크기 때문에 O(N^3)의 복잡도를 갖는 플로이드 워셜 알고리즘 보다는 O(ElogV)의 복잡도를 갖는 다익스트라 알고리즘을 활용해 문제를 풀었다.

풀이 설명

• 우선 graph를 n+1 크기로 만든다.
  • 노드의 번호를 인덱스로 그대로 사용하기 위함이다.
• heapq를 이용하여 최소힙을 통해 거리가 짧은 순으로 탐색한다.
• 만약 distance\[node] < dist라면, 즉 해당 노드까지의 거리가 heapq에서 나온 거리보다 짧다면 굳이 아래 과정을 진행하지 않고 다음 heapq의 원소로 차례를 넘긴다.
• distance\[node] < dist가 아니라면, cost를 dist에서 1이 추가된 값으로 업데이트 하고 distance[i]와 비교한다.
• 만약 cost가 더 짧다면, distance[i]를 cost 값으로 업데이트 한다.
• 또한 해당 값을 heapq에 push 한다.

python code

# 백준 1753 최단경로
from sys import stdin
import heapq

input = stdin.readline
v, e = map(int, input().split())
k = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))

INF = int(1e9)
distance = [INF] * (v+1)

def solution(v, k, graph, distance):
    queue = []
    heapq.heapify(queue)
    heapq.heappush(queue, (0, k))
    distance[k] = 0
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for x in graph[node]:
            cost = dist + x[1]
            if cost < distance[x[0]]:
                distance[x[0]] = cost
                heapq.heappush(queue, (cost, x[0]))

solution(v, k, graph, distance)

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