[Gold I] 도로포장 - 1162
준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.
문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.
입력
첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.
출력
첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.
* 접근 방법
마라톤2 문제처럼 0~k개의 포장을 다 파악하며 최소 시간을 구한다고 생각하여 dp인가 싶었고, 못 풀고 풀이를 보았다.
이 문제에서 사용되는 알고리즘은 다익스트라였다. 왜냐하면 도로까지 시간이라는 가중치가 주어지고 특정 지점까지 가장 짧은 경로를 구하는 문제였기 때문이었다.
* 해결 방법
문제에 나와있듯 graph에 양방향으로 도로 사이의 소모 시간을 체크한 후, 1번 도시부터 n번 도시까지 차례대로 0~k개 까지의 포장 수마다의 최소 시간을 구해준다.
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m, k = map(int,input().split()) # 도시, 도로, 포장
graph = [[] for _ in range(n+1)]
distance = [[INF for _ in range(k+1)] for _ in range(n+1)] # distance[n][k]
for i in range(m):
x, y, time = map(int,input().split())
graph[x].append((time, y))
graph[y].append((time, x))
def dijk(s):
heap = []
cnt = 0
distance[s][cnt] = 0
heappush(heap, (0, s, cnt))
while heap:
t, now, cnt = heappop(heap)
if distance[now][cnt] < t:
continue
for time, next in graph[now]:
next_time = time + t
if distance[next][cnt] > next_time:
distance[next][cnt] = next_time
heappush(heap, (next_time, next, cnt)) # 동일한 cnt개의 포장 상태에서 다음 도시
if cnt < k and distance[next][cnt+1] > t: # 포장 개수 증가시킨 최소거리
distance[next][cnt+1] = t
heappush(heap, (t, next, cnt+1))
dijk(1)
print(min(distance[n])) # 마지막 도로의 최소거리
'알고리즘' 카테고리의 다른 글
[Gold III] 욕심쟁이 판다 - 1937 (dfs, dp) (1) | 2023.05.14 |
---|---|
[Gold IV] 음식 평론가 - 1188 (수학, 정수론, 유클리드 호재법) (1) | 2023.05.13 |
[Gold II] 가운데를 말해요 - 1655 ( 우선순위 큐 ) (1) | 2023.05.10 |
[Gold III] 마라톤 2 - 10653 (DP) (1) | 2023.05.07 |
[Gold V] 문자 해독 - 1593 (슬라이딩 윈도우) (0) | 2023.05.06 |