[백준] 13907. 세금 (파이썬 / 파이썬)

문제 출처 : https://www.acmicpc.net/problem/13907

---

1. 문제 풀이

본 문제에 따르면, 세금 인상 횟수는 최대 3만 번까지 발생할 수 있다.

따라서 매 번 세금이 인상될 때마다 다익스트라 알고리즘을 사용한다면 직관적으로 시간초과가 날 것을 유추할 수 있다.

 

만약 A 지점에서 B 지점으로 바로 갈 수 있다고 가정하자.

그렇다면 세금이 인상된다면, 세금을 한 번만 인상하면 된다.

 

만약 A 지점에서 B 지점으로 한 번 경유해서 갈 수 있다고 가정하자.

그렇다면 길은 총 두 번 지나기에, 총 통행료를 세금 * 2만큼 인상하면 된다.

즉, 시작 지점에서 도착 지점까지 몇 개의 길을 지나서 도착했는지를 구하면 문제를 풀 수 있다.

이를 위해 다익스트라 알고리즘을 약간 변형해서 문제를 풀어보기로 하였다.

기존의 다익스트라 배열[i][j]에서 i는 출발 노드, j는 도착 노드, [i][j]는 최소 시간을 의미한다.

 

하지만, 다른 지점에서 출발하여 도착하는 경우는 알 필요가 없기 때문에, i를 지나온 길로 바꿔서 문제를 풀어보기로 하였다.

즉, 새로운 배열 dp에서, i는 지나온 길의 수, j는 도착 노드
[i][j]는 i개의 길을 지나 j 노드에 도착했을 때의 최소 통행료이다.

2. 예시

 

다음과 같은 그래프가 있다고 가정하자. (출처 : https://www.acmicpc.net/board/view/89579)

1번 노드에서 6번 노드로 갈 수 있는 경우의 수를 구해보자.

 

최초 상태

우선 1번 노드에서 출발하기 때문에, dp[0][1]을 0으로 바꿔준 후, 탐색을 시작한다.

1번 노드에서 갈 수 있는 경로는 "2번 노드"와 "4번 노드"이다.

 

- 2번 노드는 방문한 적이 없기 때문에, 2번 노드에 저장된 값은 매우 큰 값(INF)이다.

- 1번 노드 (0)에서 2번 노드로 가는 길 (3)을 지나면 3 (0 + 3)의 통행료를 내야 한다.

- 3 < INF므로, dp[1][2]를 3으로 수정해준다.

 

- 4번 노드는 방문한 적이 없기 때문에, 4번 노드에 저장된 값은 INF이다.

- 1번 노드 (0)에서 4번 노드로 가는 길 (9)를 지나면 9 (0 + 9)의 통행료를 내야 한다.

- 9 < INF므로, dp[1][4]를 9로 수정해준다.

 

첫 번째 탐색 이후

1번 노드에서 2번, 4번 노드로 갔기 때문에, 이번엔 2번, 4번 노드에서 각각 갈 수 있는 길을 탐색해보자.

 

이제 여기서 큰 고민에 빠진다. 2번 노드에서는 "1번 노드"와 "3번 노드"에 방문할 수 있다.

그렇지만 우린 1번 노드를 이미 방문했기 때문에, 1번 노드를 다시 탐색할 필요가 없다고 생각한다.

 

그렇다면 한 번 방문한 노드는 모두 다시 탐색할 필요가 없냐고 묻는다면, 정답은 "아니다".

만약 우리가 2번 노드가 아니라 4번 노드를 먼저 방문했다고 가정해보자.

4번 노드가 탐색이 완료된다면, 2번 노드에서 3번 노드를 거쳐 4번 노드에 접근할 수 없게 된다.

하지만, 1번 노드에서 4번 노드로 바로 가는 것보다, 2번, 3번 노드를 경유하여 4번 노드로 가는 것이 훨씬 빠르다.

 

그렇다면 한 번 방문한 노드를 모두 다시 탐색할 필요가 있냐면, 그것 역시 아니다.

만약 그렇다면, 1번 노드 -> 2번 노드 -> 1번 노드 -> 2번 노드 ... 와 같이 의미없는 방문이 계속될 것이기 때문이다.

따라서, 한 번 방문한 노드를 효율적으로 사용할 별개의 방법이 필요하다는 것을 알 수 있다.

2.1. 방문한 노드 사용

 

앞서 도착지까지 "n"개의 길을 지났다면, 통행료는 "n * 세금"만큼 증가한다는 점을 확인했다.

 

그렇다면 다음과 같은 상황을 생각해보자.

 

(1) 100의 통행료를 내고, 10 개의 길을 지나 도착지에 도착한 상황

(2) 101의 통행료를 내고, 1개의 길을 지나 도착지에 도착한 상황

 

세금이 부과되지 않았다면 (1)의 경우 (100 < 101)가 더 저렴하지만,

세금이 1 부과된다면 (2)의 경우 (100 + 10*1 > 101 + 1*1) 가 더 저렴하다.

 

그리고 다음과 같은 상황을 생각해보자.

 

(1) 101의 통행료를 내고, 10개의 길을 지나 도착지에 도착한 상황

(2) 100의 통행료를 내고, 1개의 길을 지나 도착지에 도착한 상황

 

세금이 부과되었든, 부과되지 않았든 어쨌든 (2)의 경우가 더 저렴하다.

그리고, 세금이 많이 부과될수록, 두 경로 사이의 격차는 더욱 커질 것이다.

즉, 더 많은 길을 지났는데 더 많거나 같은 통행료를 낸 경우에는 뭔짓을 하더라도 최소경로가 될 수 없다.

이 점을 활용하여 다시 한 번 dp 행렬을 갱신하도록 하자.

2.2. 다시 2번 노드로

그렇다면 다시 한 번 생각해보자. 2번 노드에서는 "1번 노드"와 "3번 노드"를 갈 수 있다.

 

1번 노드로 간다면 총 6의 비용 (3 + 3)이 드는데, 이는 dp[0][1] = 0보다 크기 때문에 절대 최소경로가 될 수 없다.

3번 노드로 간다면 총 5의 비용 (3 + 2)이 들고, 이는 기존에 3번 노드에 저장된 값보다 작기 때문에 갱신이 가능하다.

 

그리고 아까 1번 노드에서 4번 노드에도 갔기 때문에, 4번 노드에서는 "1번 노드", "3번 노드", "5번 노드"로 갈 수 있다.

 

한 개의 길을 지나 4번 노드에 저장된 값 (9)

- 1번 노드로 갈 경우 : 9 + 9 = 18. (18 < INF지만, 0번 만에 0의 비용으로 갈 수 있기 때문에 무시)

- 3번 노드로 갈 경우 : 9 + 1 = 10 (10 > 5므로 무시)

- 5번 노드로 갈 경우 : 9 + 1 = 10 (10 < INF므로 갱신)

 

즉, 두 번 길을 지났다면 dp 행렬은 다음과 같이 갱신할 수 있다.

3번 노드와 5번 노드가 새로 갱신되었기 때문에, 여기서 갈 수 있는 다른 경로들을 한 번 탐색해보자.

 

두 개의 길을 지나 3번 노드에 저장된 값 (5)

- 4번 노드로 갈 경우 : 5 + 1 = 6 (6 < INF and 6 < 9므로 갱신)

- 2번 노드로 갈 경우 : 5 + 2 = 7 (7 < INF지만, 한 번만에 3의 비용으로 갈 수 있기 때문에 무시)

 

두 개의 길을 지나 5번 노드에 저장된 값 (10)

- 4번 노드로 갈 경우 : 10 + 1 = 11 (11 < INF지만, 한 번만에 9의 비용으로 갈 수 있기 때문에 무시)

- 6번 노드로 갈 경우 : 10 + 1 = 11 (11 < INF므로 갱신)

 

이와 같은 작업을 계속 반복하다보면, 다음과 같은 dp 행렬을 얻을 수 있다.

즉 1번 노드에서 6번 노드로 가기 위해서는

- 3개의 길을 지나는 동안 11의 통행료를 낸다.(dp[3][6] = 11)

- 5개의 길을 지나는 동안 8의 통행료를 낸다 (dp[5][6] = 8)

 

두 가지 경우가 있음을 확인할 수 있다.

이제 도착지까지의 길의 개수와 통행료를 알기 때문에, 이를 바탕으로 세금에 따른 통행료를 구해주면 문제를 풀 수 있다.

---

3. 코드

import sys
from collections import deque
# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

# 입력값 받기
num_cities, num_roads, num_increase = map(int, input().split())
start_init, end_init = map(int, input().split())

graph = dict()

for _ in range(num_roads):
    start, dest, cost = map(int, input().split())

    if start not in graph.keys():
        graph[start] = []
    if dest not in graph.keys():
        graph[dest] = []

    graph[start].append((dest, cost))
    graph[dest].append((start, cost))

# 길 구해보자
INF = 10**9+1
dp = [[INF] * (num_cities+1) for _ in range(num_cities+1)] # dp[i][j] = i번째로 j에 갈 때의 가격
dp[0][start_init] = 0

min_values = [INF] * (num_cities+1)
min_values[start_init] = 0

queue = deque([(start_init, 0, 0)]) # 시작 지점, 비용, 경유한 노드 수

while queue:

    start_node, cost, level = queue.popleft()
    next_nodes = graph[start_node] # 해당 노드에서 갈 수 있는 노드

    for next_node, cost_to_next in next_nodes:

        cost_after = dp[level][start_node] + cost_to_next

        if cost_after >= min_values[next_node]:
            continue

        # 더 적은 비용이 없다면
        min_value = min(cost_after, dp[level+1][next_node])
        dp[level+1][next_node] = min_value
        min_values[next_node] = min_value
        queue.append((next_node, min_value, level+1))

# 도착 지점의 가중치 찾기

candidates = []

for row_idx in range(1, num_cities+1):
    if dp[row_idx][end_init] < INF:
        candidates.append([row_idx, dp[row_idx][end_init]])

# for row in dp:
#     print(row)

# 정답 출력
print(min(candidates, key = lambda x : x[1])[1]) # 최초

for _ in range(num_increase):

    answer = INF
    tax = int(input())

    for cand_idx in range(len(candidates)):
        weight, cur_sum = candidates[cand_idx]
        
        cur_sum += weight * tax
        if cur_sum < answer:
            answer = cur_sum

        candidates[cand_idx][1] = cur_sum

    print(answer)

4. 결과