[Python] 백준 1162 : 도로포장 (다익스트라, DP)

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

머리말

오랜만에 9시에 일어나서 백준 문제를 풀어봤다.

일찍 일어난거 맞지..?

어떤 문제를 풀지 고민하다가 최근 수업시간에 다루었던 다익스트라 문제를 골랐다.
1시간 30분 고민해서 풀었다가 6%에서 바로 틀렸다. 허허 아직 부족하다.

나의 접근 방법

다익스트라 문제라는 것만 생각하고 어떻게 문제에 다익스트라를 녹여낼까 고민했던 것 같다.
모든 가중치를 priority queue에 넣고 크기가 큰 순으로 weight를 0으로 집어 넣고 다익스트라를 적용시켰다.

하지만, 조금만 생각해보면 당연히 잘못된 풀이법이다. weight가 큰 것을 포장 도로로 만들 필요가 없기 때문이다.
또한 'k번 이하'라는 조건에 주의를 기울여야 했을 것이다.

해설

그렇다면, 결국 다양한 경우의 수를 다 확인해봐야 한다. 즉 이 문제는 다익스트라 + Dynamic Programming이였다. 해당 경로를 포장 도로로 만들었을 때와 만들지 않았을 때를 확인해봐야하므로, 거리의 배용을 저장하는 배열 distance를 2차원으로 정하자.

distance[i][j]에서 i는 기본 다익스트라 처럼 이동할 위치 경로 값이고, j는 해당 도로를 몇 번 포장했는 가를 나타낸다.

그 후 priority queue에 넣을 때, 다음을 고려하여 두 번 확인하면 된다.

1. 해당 경로를 포장하지 않을 때
2. 해당 경로를 포장할 때 (가중치 0이므로 덧셈 X)

🐥 이건 얻어가자

• python에서 sys.stdin.readline을 사용하면 조금 더 빠른 입력을 받을 수 있다. 그래프 문제와 같은 많은 입력을 필요로 할 때 사용하자.

코드

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

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

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

q = []
heapq.heappush(q, (0, 1, 0)) # weight, source, 도로포장횟수
distance[1][0] = 0
while q:
    dist, now, count = heapq.heappop(q)

    if distance[now][count] < dist:
        continue

    for next, weight in graph[now]:
        cost = dist + weight
        # 포장하지 않을 때
        if cost < distance[next][count]:
            distance[next][count] = cost
            heapq.heappush(q, (cost, next, count))
        # 포장할 때
        if count < k and dist < distance[next][count + 1]:
            distance[next][count + 1] = dist
            heapq.heappush(q, (dist, next, count + 1))

print(min(distance[n]))

참조

• https://4legs-study.tistory.com/24
• https://joey09.tistory.com/entry/%ED%85%8C%EC%8A%A4%ED%8A%B8%EC%BC%80%EC%9D%B4%EC%8A%A4-%EC%B6%94%EA%B0%80-%EB%B0%B1%EC%A4%80-1162%EB%B2%88-%EB%8F%84%EB%A1%9C%ED%8F%AC%EC%9E%A5-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC