[PS] BOJ 1916 / 최소비용 구하기

Minjun Kim

29 Jun 2025 • 3 min read

문제 링크: https://www.acmicpc.net/problem/1916

Thumbnail: Photo by Igor Sporynin (Unsplash)

정말 정석적인 다익스트라 구현 문제입니다.

풀이

다익스트라(Dijkstra)!

문제를 요약하면, \(N\)개의 도시(정점)과 \(M\)개의 버스(간선)이 있을 때, 시작 위치 \(S\)와 도착 위치 \(E\) 사이의 최단 거리를 구하는 문제입니다. 한 정점에서 다른 정점까지의 최단 거리를 구하는 문제라면, 다익스트라 알고리즘으로 풀 수 있습니다.

먼저 입력을 받아 그래프를 만들어야 합니다.

N = int(input())    # 도시(정점)의 개수
M = int(input())    # 버스(간선)의 개수

edges = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = map(int, input().split())
    edges[u].append((v, w))

인접 리스트로 구현한 그래프

이제 다익스트라 알고리즘을 구현해야 합니다. 그냥 구현해도 되지만, 우선순위 큐를 사용하면 시간 복잡도를 개선할 수 있습니다. 이전 글에서는 queue모듈의 PriorityQueue를 쓰라고 설명했는데, 백준 질문글에서 PriorityQueue는 매우 느리다는 설명을 보고 그냥 heapq모듈을 사용해 구현했습니다.

heapq.heappush(arr, value): arr배열에 value값을 넣습니다. 이때, value의 크기를 우선순위로 사용합니다.
heapq.heappush(arr, (priority, value)): arr배열에 priority값을 우선순위로 사용해 (priority, value)를 값으로 추가합니다.
heapq.heappop(arr): heap 구조로 저장되어있는 arr배열에서 heap 구조를 유지하면서 원소 1개를 꺼냅니다.

S, E = map(int, input().split())  # 출발지와 도착지
INF = 100_000_000_001             # 방문 불가능한 정점의 거리를 나타낼 상수
distance = [INF for _ in range(N + 1)] # 출발 정점 S로부터 각 정점 사이의 최단거리를 저장할 배열
distance[S] = 0                   # S에서 S까지의 거리는 0이다.

pq = []                           # 우선순위 큐로 사용할 배열 선언
heappush(pq, (0, S))              # (거리, 정점)
while pq:
    dist, node = heappop(pq)      # 우선순위 큐에서 원소 꺼내오기
    if distance[node] < dist: 
        continue
    for next_node, weight in edges[node]: # 다음 노드를 순회하며 우선순위 큐에 넣기
        new_dist = dist + weight
        if new_dist < distance[next_node]:
            distance[next_node] = new_dist
            heappush(pq, (new_dist, next_node))

다익스트라 알고리즘

이후 distance[E] 값을 출력해주면 됩니다.

print(distance[E])

결과 출력

전체 코드

from heapq import heappop, heappush
input = open(0).readline
N = int(input())    # 도시(정점)의 개수
M = int(input())    # 버스(간선)의 개수

edges = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = map(int, input().split())
    edges[u].append((v, w))

S, E = map(int, input().split())  # 출발지와 도착지
INF = 100_000_000_001
distance = [INF for _ in range(N + 1)]
distance[S] = 0
pq = []
heappush(pq, (0, S))  # (거리, 정점)
while pq:
    dist, node = heappop(pq)
    if distance[node] < dist:
        continue
    for next_node, weight in edges[node]:
        new_dist = dist + weight
        if new_dist < distance[next_node]:
            distance[next_node] = new_dist
            heappush(pq, (new_dist, next_node))

print(distance[E])

solution.py