[백준/1884] 고속도로 (Python)

Problem : https://www.acmicpc.net/problem/1884

1884번: 고속도로

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:08:29

 

---

 

문제 설명

 

 

봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.

다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.

 

 

입력 및 출력

 

입력

 

첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)

도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.

 

출력

 

첫 줄에 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다. 만약 가능한 경로가 없을 때에는 -1을 출력한다.

 

입력 예시

 

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

 

출력 예시

 

11

 

 

---

 

풀이

 

DP로 생각해 보자. DP[i][j]가 현재 노드 i에 남은 통행료 예산이 j인 경우의 최소 거리라고 정의하자. i에서 갈 수 있는 다른 노드 정보들(d, l, t)에 대해서, 우선 이후 통행료 j - t >= 0 을 만족해야 한다. 만약 위 전제조건을 만족한다면,

DP[d][j-t] = min(DP[d][j-t], DP[i][j] + l)

이 성립한다. 만약 최솟값으로 갱신할 수 있다면 다음 노드 d, 남은 통행료 예산 j-t, 현재 총거리 DP[d][j-t]를 토대로 다음 탐색을 진행한다.

 

여기서 더 나아가, 총거리를 기준으로 최소 힙을 사용하여 진행한다면(즉 다익스트라 알고리즘과 비슷한 순회 방법을 사용한다면) 현재 노드가 도착 노드인 시점에 최소 거리임이 보장된다. 따라서 이를 사용하여 만약 끝 노드에 도달할 수 있다면 그 거리를, 그렇지 않다면 -1을 출력하면 된다.

 

 

풀이 코드

from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline
MAX = float('inf')

K = int(input())
N = int(input())
R = int(input())

edge_dict = defaultdict(list)
for _ in range(R) :
  s, d, l, t = map(int, input().split())
  edge_dict[s-1].append((d-1, l, t))

dp = [[MAX]*(K+1) for _ in range(N)]
dp[0][K] = 0
q = [(0, K, 0)]
answer = MAX

while q :
  dist, cost, node = heappop(q)
  if node == N-1 :
    answer = min(answer, dist)
    break

  for nxt, nxt_dist, nxt_cost in edge_dict[node] :
    if cost - nxt_cost > -1 and dp[nxt][cost - nxt_cost] > dist + nxt_dist :
      dp[nxt][cost - nxt_cost] = dist + nxt_dist
      heappush(q, (dist + nxt_dist, cost - nxt_cost, nxt ))

print(answer if answer < MAX else -1)

풀이 완료!