[백준 1162] python 도로포장

 

https://www.acmicpc.net/problem/1162

1162번: 도로포장

문제 유형: 다익스트라 + dp

 

처음에는 포장할 도로를 조합하고, 이를 매번 다익스트라로 돌리려고 했다. 그리고 해당 결과물을 dp의 메모제이션 기법을 사용하려고 했으나, 어딘가 잘못됨을 느끼고 결국 구글링을해 풀이를 봤다.

 

문제의 핵심은,

1. 해당 노로 가는 경로를 '포장을 할 때' 와 '포장을 하지 않을때'로 구분 해야 한다.

2. 다익스트라의 최단거리 저장 배열(d)을 이차원 배열로 구성해야 한다. 해당 이차원 배열은 d =  [노드][도로를 포장한 횟수]로 계산한다.

3. 포장을 하지 않을 때는 [노드][현재 포장 횟수]로, 포장이 가능 해서 포장을 할때는 [노드][현재 포장 횟수+1]에 최단거리를 갱신한다. 물론 현재까지 계산된 거리 보다 새로 계산한 거리가 작아야 한다는게 기본 조건이다. 

            # 포장이 X + 비용이 더 저렴 할때
        if d[next_node][cur_k] >  cur_cost + next_cost:
            d[next_node][cur_k] = cur_cost + next_cost
            pq.append([ cur_cost + next_cost,next_node, cur_k])
            # 포장이 가능 할때 + 포장이 됐을때 비용이 더 저렴 할때
        if cur_k < k and d[next_node][cur_k+1] > cur_cost:
            d[next_node][cur_k+1] = cur_cost
            pq.append([cur_cost, next_node,cur_k+1])

 [전체 코드]

# https://www.acmicpc.net/problem/13397
import sys
import heapq
INF = sys.maxsize
input = sys.stdin.readline

n,m,k = map(int,(input()).split())
nodes =[[] for _ in range(n+1)]

for i in range(m):
    a,b,c = map(int,(input()).split())
    nodes[a].append((b,c))
    nodes[b].append((a,c))

# n*k -> k비용일때, 해당 노드의 최단거리 확인
d = [[INF for _ in range(k+1)] for _ in range(n+1)]
# 0 비용 1 목적지 node 2 포장 횟수(k)
pq = [[0, 1, 0]]

while pq:
    cur_cost, cur_node, cur_k  = heapq.heappop(pq)
    if d[cur_node][cur_k] < cur_cost: continue

    for next_node, next_cost in nodes[cur_node]:
            # 포장이 X + 비용이 더 저렴 한지
        if d[next_node][cur_k] >  cur_cost + next_cost:
            d[next_node][cur_k] = cur_cost + next_cost
            pq.append([ cur_cost + next_cost,next_node, cur_k])
            # 포장이 가능 할때 + 포장이 됐을때 비용이 더 저렴 한지
        if cur_k < k and d[next_node][cur_k+1] > cur_cost:
            d[next_node][cur_k+1] = cur_cost
            pq.append([cur_cost, next_node,cur_k+1])

print(min(d[n]))