[Python 3] BOJ - 13907 "세금"

 # 문제 링크 : https://www.acmicpc.net/problem/13907

13907번: 세금

 # 풀이 :

 개인적으로 이 문제의 핵심은 2차원 다익스트라를 이용하여 간접적인 벨만 포드를 구현하는 것이라 생각한다. 문제에서 도시의 최대 개수가 1000이라고 했으므로 일반적인 벨만 포드의 시간 복잡도인 O(N ^ 3)임을 고려할 때, 시간초과를 피할 수 없다. 따라서 최소 힙을 이용한 다익스트라로서 벨만 포드를 구현하면 시간안에 정답을 구할 수 있다. 다만, 약간 다른 점은 벨만 포드는 거쳐가는 정점 K로 나타내어 직접 거쳐가는 정점의 거리를 비교했지만, 우리가 구하려는 2차원 다익스트라는 실제로 거쳐가는 정점이 아니라, 몇 개의 정점을 거쳐갔는지로서 나타낼 것이다.

<그림 1. 임의의 그래프>

	0	1	2
0	0	INF	2
1	INF	1	INF
2	INF	5	3

 <표 1. 그림 1의 벨만포드 표>

 

 따라서 2차원 다익스트라 배열 D[i][j]의 정의는 정점 start 에서 출발하여,  정점 i를 j개의 정점을 거쳐 갈 수 있는 최소 거리가 된다. 2차원 다익스트라의 정의에 따라 D[0][0]은 정점 0을 0개의 정점을 방문하여 갈 수 있는 최소거리를 의미한다. 즉, 출발점이라는 뜻이다. D[0][2]는 정점 0을 정점 0에서 시작하여 2개의 정점을 방문하여 갈 수 있는 최소거리를 의미하는데, 그림 1에서 정점을 두번거쳐 0으로 가는 경우는 0 -> 1 -> 0 혹은 0 -> 3 -> 0이다. 전자의 경우가 후자의 경우보다 거리가 짧으므로 D[0][2]는 10이 아니라 1이 된다. 정점 0을 정점 하나만 방문해서 갈 수 있는 경우는 없으므로 INF의 갱신이 일어나지 않는다. 

 그러나 현재의 경우는 세금 징수가 일어나기 전의 상황이라고 할 수 있다. 그렇다면 매번 세금 징수가 일어날 때마다 표1을 다시 만들어야 할까? 결론적으로는 그렇지 않다. 그러나 이해를 위해 가상적으로 세금 징수 이후의 상황을 다시 고려한다고 가정한다.

<그림 2. 각 도로에 세금이 1씩 부여된 상황>

	0	1	2
0	0	INF	4
1	INF	2	INF
2	INF	6	5

<표 2. 그림 2의 벨만포드 표>

 

 이전에 D[0][2]는 2이었고 현재의 D[0][2]는 4이다. 그런데, 세금은 간선에 붙고, 한 정점에서 다른 정점으로 가려면 무조건 이어진 간선을 타고 이동해야 한다. 그런데, j번 거쳐 방문했다는 뜻은 간선을 j번 탔다는 것고 마찬가지이다. 따라서 이 사실과 2차원 다익스트라 배열의 정의를 조합한다면, 세금이 부과되었을 때, 2차원 배열 D[i][j] = D[i][j] * 세금 * j가 되며, 이 식에 따라 표1을 표2로 바꿀 수 있다. 따라서 우리는 2차원 다익스트라 배열을 초기 상태만 구해도 모든 경우를 계산할 수 있다. 추가적으로 모든 정점에 대하여 갱신이 일어 나는 것이 아니라, 도착하는 정점에 대해서만 갱신이 일어나므로 도착점이 아닌 정점에 대한 경우는 고려하지 않아도 된다.

 

 # 코드

import sys, heapq

# 입력부
vertex, edges, taxes = map(int, sys.stdin.readline().split())
start, end = map(int, sys.stdin.readline().split())

# adj : 인접 리스트, INF : 무한대, d : 2차원 다익스트라 배열
adj = [[] for _ in range(vertex)]
INF = 10000000000000000000
tax_rate = []
d = [[INF] * vertex for _ in range(vertex)]

# 최소값을 찾는 것이므로 ans를 무한대 값으로 초기화
ans = INF

# dijsta : 2차원 배열 d를 갱신시키는 함수
def dijstra(v):
    global ans
    d[v][0] = 0
    min_q = []
    min_q.append((d[v][0], v, 0))
    while len(min_q) != 0:
        distance = min_q[0][0]
        current = min_q[0][1]
        visited = min_q[0][2]
        heapq.heappop(min_q)
        flag = False
        # 불필요한 경우 1:
        # 이미 최소 거리가 있다면 굳이 정점을 더 거쳐가지 않아도 되므로
        # flag를 True로 바꿔준다
        for i in range(visited):
            if d[current][i] < distance:
                flag = True
                break
        # 불필요한 경우 2:
        # 불필요한 경우 1에서 걸려진 경우거나, 똑같이 j번째 정점을 방문해도
        # 거리가 더 작은 쪽이 유지되어야 하므로
        # 현재 거리가 배열에 저장된 거리보다 크다면 굳이 갱신이 일어나지 않는다
        if flag or d[current][visited] < distance:
            continue
        # 불필요한 경우 3:
        # 애초에 현재 정점이 도착정점이라면 굳이 다른 정점을 탐색하지 않아도 된다
        if current == end - 1:
            ans = min(ans, d[current][visited])
            continue
        for i in range(len(adj[current])):
            next = adj[current][i][0]
            nextdistance = adj[current][i][1] + distance
            # 배열 d의 범위를 벗어나지 않고 거리가 더 작다면 갱신
            if visited + 1 < vertex and nextdistance < d[next][visited + 1]:
                d[next][visited + 1] = nextdistance
                heapq.heappush(min_q, (nextdistance, next, visited + 1))

# 인접리스트 생성
for i in range(edges):
    a, b, w = map(int, sys.stdin.readline().split())
    adj[a - 1].append([b - 1, w])
    adj[b - 1].append([a - 1, w])

# 세금 입력
for i in range(taxes):
    tax_rate.append(int(sys.stdin.readline()))

# 다익스트라 실행
dijstra(start - 1)

# 세금이 부과되지 않은 경우 정답 출력
print(ans)

# 도착 정점에 대한 경우만 세금률에 따라 갱신
for i in tax_rate:
    for j in range(vertex):
        if d[end - 1][j] != INF:
            d[end - 1][j] = d[end - 1][j] + i * j
    # 각 세금률에 따른 정답 출력
    print(min(d[end - 1]))