백준 파이썬 1916번 최소비용 구하기 (Today I Learn 2025.10.12)

백준 파이썬 공부 2025.10.12
1916번 최소비용 구하기 (골드 5)

1. 문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 
우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 
A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 
도시의 번호는 1부터 N까지이다.

2. 입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 
둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 
그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 
먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 
그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 
버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 
출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

3. 출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

4. 문제 풀이
최소 비용 루트를 찾는 문제이다.
BFS와 DP를 이용하여 문제를 풀어보려고 했으나 메모리 초과가 발생하였다.

>>>메모리 초과

"""
1916번 최소비용 구하기
입력 : n (도시 수), n (버스 수), bus (버스 비용)
s, e (시작점, 도착지)
출력 : 목적지로 가는 최소 비용
"""
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    depart, arrive, fee = map(int, input().split())
    bus[depart].append((arrive, fee))
    
s, e = map(int, input().split())

def BFS():
    queue = deque()
    queue.append((s, 0))
    
    DP = [0] * (n+1)
    while queue:
        city, cost = queue.popleft()
        
        if city == e:
            if DP[city] == 0:
                DP[city] = cost
            elif DP[city] > cost:
                DP[city] = cost
        
        else:
            for arrive, fee in bus[city]:
                queue.append((arrive, cost+fee))
    
    return DP[e]
    
print(BFS())

코드를 돌려 보았을때 결과는 동일하게 나오지만,
메모리 오류가 나온다. 메모리 오류의 원인은 너무 많은 queue의 생성으로 예상되어,
queue가 삽입되는 조건을 조금 더 엄격하게 제한하였다.

- 해당 도시에서 출발하는 경우에, 
이미 기록된 비용보다 popleft된 비용이 높으면 queue를 추가하지 않고 다음 queue로 넘어갔으며
- queue를 삽입할 때, 해당 도착지에 도달할 비용이 기록된 비용보다 작을 경우에만 추가하였다

>>> 정답 코드

"""
1916번 최소비용 구하기
입력 : n (도시 수), n (버스 수), bus (버스 비용)
s, e (시작점, 도착지)
출력 : 목적지로 가는 최소 비용
"""
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    depart, arrive, fee = map(int, input().split())
    bus[depart].append([arrive, fee])
    
s, e = map(int, input().split())

def BFS():
    queue = deque()
    queue.append((s, 0))
    
    DP = [1e9] * (n+1)
    while queue:
        city, cost = queue.popleft()
        if DP[city] < cost:
            continue
        
        for arrive, fee in bus[city]:
            if DP[arrive] > cost + fee:
                DP[arrive] = cost + fee
                queue.append([arrive, cost+fee])
    
    return DP[e]
    
print(BFS())

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