백준 1916번 - 최소비용 구하기

최소비용 구하기 문제 바로 가기

풀이 날짜: 2026-01-23

baekjoon 알고리즘 문제 풀이

풀이 코드

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

start, end = map(int, input().split())

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        now_dist, now = heapq.heappop(q)
        if distance[now] < now_dist:
            continue
        for i in graph[now]:
            cost = now_dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))
dijkstra(start)

print(distance[end])
print(count)  

문제 핵심 요약:

이 문제는 도시 간 이동 비용이 주어졌을 때, 출발 도시에서 도착 도시까지의 최소 비용을 구하는 전형적인 최단 경로 문제다. 모든 간선의 가중치가 양수이므로, 한 번 선택한 최소 비용 경로가 이후에 더 줄어들지 않는 다익스트라 알고리즘을 적용할 수 있다.

그래프 및 거리 배열 설계

도시를 노드, 버스를 간선으로 보는 방향 그래프로 문제를 모델링했다. graph[a] = [(b, c)] 형태로 저장하여, a 도시에서 b 도시로 이동할 때의 비용 c를 함께 관리한다. 각 도시까지의 최소 비용을 저장하기 위해 distance 배열을 사용하고, 초기값은 매우 큰 값(INF)으로 설정해 아직 방문하지 않았음을 표현했다.

우선순위 큐를 이용한 다익스트라

다익스트라의 핵심은 “현재까지 비용이 가장 적은 도시부터 처리한다”는 점이다. 이를 위해 (현재 비용, 도시 번호) 형태로 우선순위 큐(heap)를 사용한다. 큐에서 꺼낸 도시가 이미 더 짧은 거리로 처리된 적이 있다면(distance[now] < now_dist), 해당 상태는 무시하여 불필요한 연산을 줄인다.

거리 갱신 과정

현재 도시에서 갈 수 있는 모든 인접 도시를 확인하며, 현재까지 비용 + 이동 비용이 기존에 저장된 거리보다 짧다면 갱신한다. 이 과정을 통해 최단 거리 후보만 큐에 다시 넣게 되고, 결국 도착 도시의 최소 비용이 확정된다.

최종 결과 출력

최소 비용만 출력하면 되므로, 모든 탐색이 끝난 후 distance[end]를 출력한다.