[백준] #1753 최단경로(python)

수영·2022년 8월 11일

Python3 다익스트라 백준

백준

목록 보기

33/117

📌문제

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

예제 입력

예제 출력

0
2
3
7
INF

백준 1753번 문제

💡Idea

다익스트라 알고리즘을 그대로 구현하는 문제입니다.

다익스트라 알고리즘이 궁금하다면?!

이 문제는 순차 탐색을 하면 시간 초과가 나기 때문에, 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하였습니다.

💻코드

⏰ 시간 : 712 ms / 메모리 : 66916 KB

import heapq
import sys
input = sys.stdin.readline

INF = sys.maxsize # 최댓값 설정
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()) # u에서 v로 가는 weight w
    graph[u].append((v, w))

def dijkstraHeapQ(start):
    distance = [INF for _ in range(V+1)] # 모든 노드의 최단 거리 무한대로 설정
    distance[start] = 0 # 시작 노드의 최단 거리는 0
    hq = [(0, start)] # 우선순위 큐
    while hq:
        dis, node = heapq.heappop(hq)
        if distance[node] < dis: # 이미 node의 더 짧은 최단거리가 있는 경우 무시
            continue
        for n, d in graph[node]:
            if distance[n] > distance[node] + d: # 더 짧은 최단거리 발견 시 갱신 및 큐 삽입 
                distance[n] = distance[node] + d
                heapq.heappush(hq, (distance[n], n))
    return distance

dh = dijkstraHeapQ(K)
for i in range(1, V+1):
    print(dh[i] if dh[i] != INF else "INF")

📝코드 설명

우선순위 큐를 사용하여 다익스트라 알고리즘을 구현한 코드입니다.

graph는 각 노드들이 갈 수 있는 노드들의 리스트를 저장해둔 리스트입니다.
u에서 w의 weight로 v로 이동할 수 있다면, graph의 u번째 인덱스에는 (v, w)가 저장되어 있습니다.

distance는 각 노드들의 최단 거리를 저장해두는 리스트입니다.
처음에는 시작노드를 제외하고 모든 노들의 최단 거리를 무한댓값으로 초기화합니다.

hq는 우선순위 큐입니다. 우선순위 큐에는 지금까지 찾아낸 정점에서의 노드의 최단 거리와 노드의 번호를 함께 넣어줍니다.
우선순위 큐에 시작노드의 최단 거리인 0과 시작노드를 넣어준 뒤, 우선순위 큐를 통한 탐색을 시작합니다.

가장 최단 거리가 작은 노드를 pop합니다.
(우선순위 큐의 경우, 넣어진 쌍의 첫 번째 요소를 기준으로 정렬을 해줍니다.)

만약 pop된 node의 최단 거리보다 이미 갱신된 distance의 거리가 더 짧다면 무시하고 다시 pop 해줍니다.

그렇지 않다면 graph[node]를 통해 node에서 갈 수 있는 다른 노드들을 찾습니다. 각 노드들은 n, node에서 n까지의 거리를 d라고 하여 반복문을 돌며, 시작 노드에서 해당 노드까지의 최단 거리인 distance[node]와 해당 노드에서 다른 노드로 가는 거리d의 합과 distance[n]의 거리를 비교합니다.
만약, 원래의 distance[n]의 거리가 더 길다면 새로운 짧은 값으로 갱신해준 뒤 우선순위 큐에 넣어줍니다.

큐에 아무 노드도 들어가지 않을 때까지 위의 과정을 반복하면 됩니다.

최단 거리를 모두 찾았다면, INF의 값을 가지고 있는지 확인하며 출력해줍니다.