백준 1916 - 최소비용 구하기(Python)

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

문제

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

입력

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

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

출력

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

풀이

출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어지고 버스로 이동하는 거 이외에 이동하는 다른 방법은 없다. 즉, 무조건 정해진 버스 경로로만 이동이 가능합니다.

1️⃣ 먼저, 일반적인 heapq 사용한 다익스트라 풀이를 적용했습니다.

• 현재 위치와 현재 위치까지의 비용을 heap에 저장
• 현재 위치가 도착 위치라면 min_pay 변수(최소 비용) 를 갱신

import sys 
import heapq
input = sys.stdin.readline 

n = int(input())
m = int(input())

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

for _ in range(m):
    s, e, p = map(int, input().split()) # start, end, pay
    distance[s].append((e,p))

start, end = map(int, input().split())
heap = []
heapq.heappush(heap, (0, start))
min_pay = float('inf')

while heap:
    dist, start = heapq.heappop(heap)

    if start == end: # 도착지점이면 
        min_pay = min(min_pay, dist)
        continue 

    for end_place, pay in distance[start]:
        heapq.heappush(heap, (dist + pay, end_place))

print(min_pay)

⇒ 메모리 초과

2️⃣ 무조건 정해진 버스 경로로만 이동해야 하기에 이미 한번 지나온 도시라면 다시 그곳을 갈 필요는 없습니다.

• 방문 여부를 표시해주는 visited를 생성하여 현재 위치가 되었을 때 visited = True로 설정
  

import sys 
import heapq
input = sys.stdin.readline 

n = int(input())
m = int(input())

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

for _ in range(m):
    s, e, p = map(int, input().split()) # start, end, pay
    distance[s].append((e,p))

start, end = map(int, input().split())
min_pay = float('inf')

visited = [False for _ in range(n+1)]

heap = []
heapq.heappush(heap, (0, start))

while heap:
    now_pay, city = heapq.heappop(heap)
    visited[city] = True

    if city == end:
        min_pay = min(min_pay, now_pay)
        continue 

    for end_city, pay in distance[city]:
        if not visited[end_city]: # 아직 방문하지 않았다면 
            heapq.heappush(heap, (now_pay+pay, end_city))

print(min_pay)

⇒ 시간 초과

3️⃣ 현재 위치의 pay와 앞으로 연결될 도시와의 비용의 합이 기존 도착 도시의 최소 비용보다 크다면 굳이 갱신할 필요가 없습니다. 만약 그게 아니라면 새롭게 오는 비용이 최소 비용이 되니 갱신해줘야합니다.

• pay_list로 각 도시별 최소 비용 저장할 리스트 생성
• pay_list는 최소 비용값으로 갱신해야 하니 inf로 초기화
• 현재 위치의 비용 (now_pay)과 도착할 위치까지의 비용(pay)의 합이 도착 위치의 최소 비용보다 크다면 continue
• 작다면 now_pay + pay 값으로 도착 위치의 최소 비용 갱신

import sys 
import heapq
input = sys.stdin.readline 

n = int(input())
m = int(input())

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

for _ in range(m):
    s, e, p = map(int, input().split()) # start, end, pay
    distance[s].append((e,p))

start, end = map(int, input().split())
min_pay = float('inf')

visited = [False for _ in range(n+1)]
pay_list = [float('inf') for _ in range(n+1)]
pay_list[start] = 0 # 혹시 몰라서 
heap = []
heapq.heappush(heap, (0, start))

while heap:
    now_pay, city = heapq.heappop(heap)
    visited[city] = True

    if city == end:
        min_pay = min(min_pay, now_pay)
        continue 

    for end_city, pay in distance[city]:
        if now_pay+pay >= pay_list[end_city]:
            continue
        if not visited[end_city]: # 아직 방문하지 않았다면 
            pay_list[end_city] = now_pay+pay
            heapq.heappush(heap, (now_pay+pay, end_city))

print(min_pay)

⇒ 17% 시간 초과

해당 문제는 0.5초라 시간 초과가 계속 걸려서 어떻게 줄일까 고민을 하다가

값을 계산할 때만 heap을 쓰지 말고 처음 도착 위치와 버스 비용을 distance에 저장할 때도 heap을 활용하면 어떨까를 생각해냈습니다.

그렇게 하면 추후에 distance에서 연결된 경로를 비용이 적은것부터 나올 수 있지 않을까 하는 아이디어에서 시작한 이 내용은

import sys 
import heapq
input = sys.stdin.readline 

n = int(input())
m = int(input())

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

for _ in range(m):
    s, e, p = map(int, input().split()) # start, end, pay
    heapq.heappush(distance[s], (e,p))

start, end = map(int, input().split())
min_pay = float('inf')

visited = [False for _ in range(n+1)]
pay_list = [float('inf') for _ in range(n+1)]
pay_list[start] = 0
heap = []
heapq.heappush(heap, (0, start))

while heap:
    now_pay, city = heapq.heappop(heap)
    visited[city] = True

    if city == end:
        min_pay = min(min_pay, now_pay)
        continue 

    for end_city, pay in distance[city]:
        if now_pay+pay >= pay_list[end_city]:
            continue
        if not visited[end_city]: # 아직 방문하지 않았다면 
            pay_list[end_city] = now_pay+pay
            heapq.heappush(heap, (now_pay+pay, end_city))

print(min_pay)

⇒ 성공 ✨

와 충격 진짜다 이거다