문제 정보
- 문제 번호 : 1162
- 문제 이름 : 도로 포장
- 문제 링크 : https://www.acmicpc.net/problem/1162
- 정답 코드 : https://github.com/dalmengs/algorithm-solutions/blob/main/1162/main.py
- 난이도 : Platinum 5
- 체감 난이도 : Gold 2
- 알고리즘 : DP, 그래프, 다익스트라
문제 설명
1번이 시작점, N번이 도착점인 그래프가 있다.
이 그래프는 항상 1번에서 N번 정점에 도달할 수 있는 형태로 주어진다.
각 정점을 잇는 간선에는 비용이 있는데, 최대 K개의 간선을 골라 간선의 비용을 0으로 만들 수 있다.
이때 1번으로 N번으로 가는 최단 경로를 구하는 문제이다.
문제 해결
일단 그래프에서의 최단 경로를 구해야 하기 때문에 다익스트라 알고리즘을 떠올렸다.
최단 거리를 저장하는 배열에 현재 정점까지 오면서 몇 개의 간선을 골랐는지 정보를 저장하여 2차원 배열로 최단 거리/선택 간선 개수 정보를 저장했다.
우선순위 큐를 사용하는 다익스트라 알고리즘에서 큰 변화 없이 그대로 사용하면 되고, 다음 상태로 전이시킬 때, 간선을 고르는 경우와 고르지 않는 경우로만 나누어서 상태를 전이시켜주면 된다.
정답 코드
Python
import heapq
INF = 9876543212345
n, m, k = map(int, input().split())
g = { i: [] for i in range(1, n + 1)}
for i in range(m):
u, v, t = map(int, input().split())
g[u].append([v, t])
g[v].append([u, t])
dp = [[INF for _ in range(k + 1)] for _ in range(n + 1)]
q = []
heapq.heappush(q, (0, 1, 0))
dp[1][k] = 0
while len(q):
now = heapq.heappop(q)
now_cost = now[0]
now_node = now[1]
now_count = now[2]
if dp[now_node][now_count] < now_cost:
continue
for nxt in g[now_node]:
next_node = nxt[0]
next_cost = nxt[1]
# 다음 도로 포장
if now_count < k:
if dp[next_node][now_count + 1] == INF or now_cost < dp[next_node][now_count + 1]:
dp[next_node][now_count + 1] = now_cost
heapq.heappush(q, (now_cost, next_node, now_count + 1))
# 다음 도로 포장하지 않음
if dp[next_node][now_count] == INF or now_cost + next_cost < dp[next_node][now_count]:
dp[next_node][now_count] = now_cost + next_cost
heapq.heappush(q, (now_cost + next_cost, next_node, now_count))
print(min(dp[n]))마무리
그래프에서 최단 거리를 구해야 하므로 다익스트라 알고리즘을 떠올려야 하고, 선택한 간선의 개수를 같이 저장하여 현재 상태를 기반으로 다음 상태를 판단해주는 DP 기법을 조금만 활용하면 쉽게 풀 수 있다.
댓글 남기기