[🥇5 / 백준 1753 / 파이썬] 최단경로

 

1753번: 최단경로

 

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

 

예제 입력  5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6

예제 출력  0 2 3 7 INF

 

풀이

 

다익스트라 알고리즘을 활용하여 시작 정점에서 나머지 각각의 정점까지 최단거리들을 찾는 문제이다.

우선 다익스트라 알고리즘을 모르는 채로 문제를 푸는 것은 불가능하여 공부한다는 느낌으로 풀었다.

 

다익스트라 알고리즘은 그래프에서 정점간의 최단 거리를 찾는 알고리즘이다.

단, 다익스트라에선 대부분 일반적인 큐가 아닌 우선순위 큐를 활용한다.

 

왜 큐가 아닌 우선순위 큐를 활용해야 할까? 라는 의문이 들었었다.

다익스트라 알고리즘을 잘못 이해한 데서 나오는 의문이었다.

아래의 설명이 같은 의문을 가진 분들에게 도움이 될 것이다.

 

 

위의 그림을 보자.

정점 1에서 3까지 가는 최단 경로를 찾을 것이다.

 

정점 1에서 3까지 가는 방법은 2가지가 있다.

 

1 → 2 → 3

1 → 3

 

이렇게만 보면 쉽지만, 우리는 정점이 약 30만개일 때에도 최단 경로를 찾아야 하므로

당장은 어떻게 가는 방법이 더 빠른지 모른다고 가정하도록 하자.

 

먼저 준비해야 할 것은 2가지이다.

하나는 정점 간의 인접 리스트,

하나는 각 정점까지의 거리를 담은 배열이다.

 

인접 리스트를 생성할 때 주의할 점은 일반 BFS와 달리 연결된 정점과 간선의 가중치도 함께 넣어야 한다는 것이다.

 

거리 배열 이름은 dist라 하겠다. 크기는 정점의 개수이다.

다른 정점까지의 거리는 아직 모르므로 무한대라고 가정한다.

따라서 dist = [inf, inf, inf] 와 같이 구성될 것이다.

 

이제 힙에 시작 정점과 거리를 넣어준다.

튜플로 (시작 정점부터 해당 정점까지의 거리, BFS 수행 정점) 를 넣어줄 것이다.

위의 튜플 순서는 다익스트라를 수행함에 있어서 매우 중요하다.

 

시작 정점까지의 거리는 자기 자신이므로 0에 해당한다.

따라서 (0, 1) 이 힙에 들어간다. (인덱스 순서상 0이지만 알아보기 쉽게 1이라고 하자.)

 

 

이제 다익스트라 알고리즘을 수행한다!

힙에 원소가 남아있으므로 힙의 최상단에 있는 튜플을 빼온다.

 

당연하지만 시작 정점에서 정점1까지의 거리는 0이라고 한다.

이는 dist[0] 인 inf 보다 작다.

따라서 dist[0]을 0으로 고쳐주도록 하고, 힙에 push하는 과정을 수행한다.

(만약 dist[0]보다 현재까지의 거리가 크다면

위의 과정은 생략하고 다음 heap 원소를 가져오면 된다.)

 

정점 1에서 BFS를 수행해야 한다.

인접 리스트를 참고하니 2, 3 정점과 연결되어 있다고 한다.

따라서 1에 연결되어있는 2, 3 정점의 정보를 가져온다.

 

올려보기 힘들 것 같아서 다시 가져왔다.

 

2까지의 가중치는 2

3까지의 가중치는 7이다.

 

이것들의 가중치와 현재까지의 거리를 더하여 heap에 넣어주도록 하자.

따라서 힙엔 (0+2, 2), (0+7, 3) 이 들어가게 된다.

 

이제 힙엔 (2, 2), (7, 3) 이 들어 있다.

힙은 최소 원소가 가장 위에 있게 되므로 다음 다익스트라 루프에선 (2, 2) 가 선택된다.

 

시작 정점에서 정점 2까지의 거리는 2로, inf 보다 작다.

따라서 dist[1]엔 2가 기록되고 정점 2의 인접 리스트에 있는 3을 가져온다.

그리고 힙엔 (2+4, 3) 이 들어가게 된다.

 

이제 힙엔 (6, 3), (7, 3) 이 남아있다.

 

여기서 왜 일반 큐 대신 우선순위 큐가 필요한지 나타난다.

바로 시작 정점에서 거리가 가장 가까운 것들만 우선적으로 뽑아 쓰겠다는 것이다!

 

일반 BFS를 수행했다면 큐에 들어온 순서대로 진행될 것이므로 정점 3까지의 거리는 7로 먼저 기록될 것이다.

이를 힙 자료구조로 쉽게 방지하고 최단 경로만을 빠르게 찾는 것이다.

 

여기까지 잘 따라왔다면 나머지 과정은 후술하지 않아도 추론할 수 있을 것이다.

아직 부족한 실력이지만 읽어준 분들께 많은 도움이 되길 바란다.

 

 

아래는 필자에게 많은 도움이 되었던 글의 링크이다.

4-3 의 실수를 범했었는데, 코드를 다시 작성하며 확실하게 짚고 넘어갈 수 있었다.

https://www.acmicpc.net/board/view/34516

 

처음 작성한 코드

수행시간 2392ms

import heapq
import sys
input = sys.stdin.readline

v,e = map(int,input().split())
start = int(input())-1
dist = [float('inf') for i in range(v)]
dist[start] = 0

linked = [[] for i in range(v)]
for i in range(e):
    a,b,w = map(int,input().split())
    linked[a-1].append((w,a-1,b-1))

heap = []
for w,a,b in linked[start]:
    heapq.heappush(heap, (0,w,a,b))
    
while(heap):
    d,w,a,b = heapq.heappop(heap)
    if dist[a]+w < dist[b]:
        dist[b] = dist[a]+w
        for w,x,y in linked[b]:
            heapq.heappush(heap,(dist[b],w,x,y))
            
for i in dist:
    print(i if i != float('inf') else "INF")

 

다시 공부하며 보완한 코드

수행시간 896ms

import heapq
import sys
input = sys.stdin.readline

v,e = map(int,input().split())
start = int(input())-1
dist = [float('inf')] * v
dist[start] = 0

linked = [[] for i in range(v)]
for i in range(e):
    a,b,w = map(int,input().split())
    linked[a-1].append((b-1,w))

heap = []
heapq.heappush(heap, (0,start))
    
while(heap):
    curDist,curNode = heapq.heappop(heap)
    if dist[curNode] < curDist:
        continue
        
    for toNode, toDist in linked[curNode]:
        d = curDist + toDist
        if dist[toNode] > d:
            dist[toNode] = d
            heapq.heappush(heap, (d, toNode))
            
for i in dist:
    print(i if i != float('inf') else "INF")