[baekjoon] 1162 도로포장

[baekjoon] 1162 도로포장

문제

기본적으로는 그래프 상에서 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]))

from http://be-simon.tistory.com/8 by ccl(A) rewrite - 2021-08-05 23:26:31