[baekjoon] 1162 도로포장

1162 도로포장 Link

문제

---

기본적으로는 그래프 상에서 1번 -> N번 노드까지 이동하는 최단거리를 구하는 문제이다.
거기에 K개의 도로를 포장해서 소요시간을 0으로 만들어버릴 수 있다는 추가 조건을 고려해야한다.

접근

---

가중치는 시간 이기 때문에 항상 양수이고 기본 알고리즘은 다익스트라를 사용하면 된다.
거기에 고려해야할 점은 K개의 edge의 weight를 0으로 만들 수 있다 라는 것.
그리고 꼭 K개를 채워서 포장할 필요는 없다.

자주 나오는 문제 유형인데, 다익스트라도 DP 기반이니까 2차원 DP를 쓰면 된다.
2차원 DP 배열에서 row는 node 번호를 가리키고, column은 포장한 도로의 개수를 나타내서
최종적으로 dp[i][j] 는 1 -> i 번 노드로 이동하는데 도로 포장을 j번 했을 때의 최소 시간 을 나타낸다.

그 다음에는 기존 다익스트라와 동일하게 min heap을 하나 운영하면서 최소 시간을 갱신해나간다.
heap에는 city, 1 -> city로 가는데 걸리는 시간, 그리고 이 때의 포장 횟수 가 들어가야한다.
그리고 heap에서 어떤 노드를 뽑았을 때, 인근 city들로 이동하면서 그 길을 포장하는 경우 와 포장하지 않는 경우 를 따로 갱신해줘야한다.
이렇게 하면 dp[N]에 1 -> N 까지 이동하는데 걸리는 최소 시간이 포장 횟수 별로 저장되게 된다.
포장을 꼭 K번 할 필요는 없으니 그 중에 최소값이 정답이 된다.

Code

import sys
from heapq import heappush, heappop
from math import inf
input = sys.stdin.readline

N, M, K = map(int, input().split())

# dp[][] -> 1 ~ N까지 가는데 K개 포장을 써서 가는 최소값
dp = [[inf for _ in range(K + 1)] for _ in range(N + 1)]
g = [[] for _ in range(N + 1)]

for _ in range(M):
    s, e, t = map(int, input().split())
    g[s].append([e, t])
    g[e].append([s, t])

dp[1][0] = 0
h = [(0, 1, 0)] # time, cur, k
while h:
    time, city, kcnt = heappop(h)
    if dp[city][kcnt] < time:
        continue

    for e, t in g[city]:
        nt = time + t
        # 이번엔 포장 안함
        if nt < dp[e][kcnt]:
            dp[e][kcnt] = nt
            heappush(h, (nt, e, kcnt))

        # 이번에 포장하는 경우
        nt = time
        if kcnt < K and nt < dp[e][kcnt + 1]:
            dp[e][kcnt + 1] = nt
            heappush(h, (nt, e, kcnt + 1))

print(min(dp[N]))