[골드 5] 백준 14284 - 간선 이어가기 2 (파이썬)

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

풀이

이 문제는 조금 방향 없는 그래프, 즉 무방향 그래프가 주어지며, 정점수 N, 간선수 M이 주어진다.

각 간선은 가중치를 가지며, 출발점 S에서 도착점 T까지의 최단 거리를 구하는 문제이다.

이 문제에세의 핵심 알고리즘은, 단연코 다익스트라 알고리즘이라고 할 수 있다.

먼저 가중치가 있는 그래프에서 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며, 이 문제에서는 특정 시작점에서 특정 도착점 까지의 거리만 구하면 된다.

from queue import PriorityQueue

우선순위 큐는 최소 거리 기준으로 정점을 꺼내기 위해서 위와 같이 사용한다.

N, M = map(int, input().split())
adj = [[] for _ in range(N)]

정점수와 간선수 및 인접 리스트 방식으로 그래프를 저장하기 위해서 위와 같이 선언한다.

for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    adj[a].append((b, c))
    adj[b].append((a, c))

위와 같이 간선 정보를 입력받으며, 양방향 간선이므로, adj[a], adj[b]에 각각 추가한다.

S, T = map(int, input().split())
S, T = S - 1, T - 1

시작점 S, 도착점 T 입력 및 1-Base-Index를 0-Based-Index로 수정한다.

dist = [1e9] * N
pq = PriorityQueue()

pq.put((0, S))
dist[S] = 0

dist의 경우 시작점에서 각 정점까지의 최단 거리를 저장하며, 시작점 S는 거리 0으로 초기화, 나머지는 무한대로 미리 초기화 해둔다.

또한 우선순위 큐에 (거리, 정점) 형태로 삽입한다.

while pq.qsize() != 0:
    d, u = pq.get()

    if d != dist[u]:
        continue

큐에서 현재 가장 거리가 짧은 정점 u를 꺼내며, 꺼낸 값 d가 dist[u]와 다르면 이미 더 짧은 거리로 처리되었으므로 스킵한다.

    for v, w in adj[u]: 
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

인접한 정점 v에 대해서 현재까지 알려진 거리보다 더 짧은 경로가 있으면 업데이트한다.

print(dist[T])

마지막으로 dist[T]를 출력하면 S에서 T까지의 최단 거리를 출력 하는 것이다.

시간 복잡도

O(M Log N) → 우선순위 큐 기반 다익스트라 사용

코드

# 백준 14284 - 간선 이어가기 2
# 분류 : 다익스트라

import sys
from queue import PriorityQueue

input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N)]

for _ in range(M) :
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1

    adj[a].append((b, c))
    adj[b].append((a, c))

S, T = map(int, input().split())
S, T = S - 1, T - 1

dist = [1e9] * N
pq = PriorityQueue()

pq.put((0, S))
dist[S] = 0

while pq.qsize() != 0 :
    d, u = pq.get()

    if d != dist[u] :
        continue
    
    for v, w in adj[u]: 
        if dist[v] > dist[u] + w :
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

print(dist[T])