[파이썬/Python] 백준 11779(🥇3): 최소비용 구하기 2

숨·2025년 8월 13일

코테

알고리즘 문제 풀이

목록 보기

111/128

📌 문제 : 백준 11779

📌 문제 탐색하기

n : 도시의 개수 ( $1 ≤ n ≤ 1000$ )
m : 버스의 개수 ( $1 ≤ m ≤ 100000$ )

문제 풀이

출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제이다.
최소 비용과 함께 그 경로에 해당하는 도시 개수와 지나는 순서대로 도시 번호를 출력해야 한다.

입력에 따라 각 도시의 연결 정보와 가중치를 저장하고, 최소 비용과 경로를 저장할 리스트를 정의한다.

그래프 구조에서 최소 가중치를 찾는 문제이므로 다익스트라를 구현한다.

힙 구조를 활용해 BFS와 유사한 구조로 구현한다.

특징	BFS	다익스트라
간선 가중치	모두 동일 (1)	다양하게 가능
큐 종류	FIFO 큐	우선순위 큐 (힙)
최소 비용 보장	단계별 방문으로 보장	비용 기준 방문으로 보장
시간복잡도	O(n+m)	O((n+m) log n)

가능한 시간복잡도

힙 연산 → $O((n+m)logn)$
while 내 간선 탐색 → $O(m)$

최종 시간복잡도
최악일 때 $O((n+m)logn) = O(10^5 * log(10^3))$ 이 되는데 이는 제한시간 1초 내 충분히 수행 가능하다.

알고리즘 선택

heapq로 다익스트라 구현해 최소 비용 탐색

📌 코드 설계하기

다익스트라 구현
입력받기
비용, 경로 저장할 리스트 정의
다익스트라 실행
출력

📌 시도 회차 수정 사항

1회차

최소 비용이라는 생각에 최단 거리를 생각해서 BFS를 사용하려 했었다. 생각해보니 그래프의 가중치를 활용한다는 부분에서 다익스트라를 사용해야 한다는 것을 깨달았다. 다익스트라를 까먹어서 관련 풀이를 생각해내지 못했다.

📌 정답 코드

import sys
import heapq

input = sys.stdin.readline

# 무한 의미
INF = int(1e9)


# 다익스트라 구현
def dijkstra(start, end):
    queue = []
    # 시작 도시 비용 0
    heapq.heappush(queue, (0, start))
    # 시작 도시 최소 비용
    costs[start] = 0

    while queue:
        cost, city = heapq.heappop(queue)

        # 이미 더 낮은 비용으로 방문한 적 있으면 무시
        if costs[city] < cost:
            continue

        # 연결 도시 확인
        for next_city, next_cost in graph[city]:
            # 누적 비용 계산
            new_cost = cost + next_cost
            # 더 작은 비용이면 갱신
            if new_cost < costs[next_city]:
                costs[next_city] = new_cost
                prev[next_city] = city
                heapq.heappush(queue, (new_cost, next_city))

    # 경로 저장
    path = []
    now = end
    while now != -1:
        path.append(now)
        now = prev[now]
    path.reverse()

    return costs[end], path


# 입력 받기
n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end, cost = map(int, input().split())
    graph[start].append([end, cost])

want_start, want_end = map(int, input().split())

# 최소 비용 저장할 리스트 정의
costs = [INF] * (n + 1)

# 경로 저장 리스트 정의
prev = [-1] * (n + 1)

# 다익스트라 실행
min_cost, path = dijkstra(want_start, want_end)

# 출력하기
print(min_cost)
print(len(path))
print(*path)

결과

✏️ 회고

자신있게 BFS를 선택했지만 조금만 공부했다면 누가봐도 다익스트라로 해결할 수 있는 문제였다. BFS가 조금 익숙해졌다고 무조건 이 풀이만 생각해내는 것 같다. 조금 더 다양한 문제를 풀려고 해야 겠다. 다익스트라도 익숙해질 수 있도록 하면서 BFS/DFS와 헷갈리지 않게 해야 겠다.