반응형

[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])) # 마지막 도로의 최소거리

+ Recent posts