백준 1005번 : ACM Craft in Python
이 문제는 위상 정렬 문제를 좀더 발전시킨 문제로, 위상 정렬을 통한 그래프 탐색에서 목표 정점까지 도달하는데 걸리는 시간의 최소값을 구해야 하는 문제이다.
이전의 줄 세우기 문제처럼 DFS를 사용해 위상 정렬을 하는 것은 단순히 어떤 순서대로 정점을 방문하는 것이 좋은지를 알려주는 것이기에, 이러한 문제의 경우에는 다른 방식으로 위상 정렬을 해야 한다. 이 방법은 기존의 DFS를 사용하는 것보다 더 직관적이고 이를 응용하는 것도 더 쉽다.
위상 정렬의 또다른 방법은 바로 정점들에 사전에 방문해야 하는 정점의 수를 나타내는 degree를 부여하고 degree가 0인 정점들의 queue를 만드는 것이다. 즉, 사전에 방문해야 하는 정점이 없는 정점부터 방문하면서 다른 정점들의 방문 조건을 만족시킨 뒤 그 정점에 방문하는 것을 반복해 결과적으로 모든 정점들을 방문해 나가는 방식이다.
예를 들어 1 -> 2 -> 3으로 그래프가 주어졌다고 할 때 정점 1의 degree는 0, 정점 2와 정점 3은 degree가 1이다. 이때 정점 1을 방문하면 정점 1과 인접한 정점 2의 degree를 1 줄이고, degree가 0이 된 정점 2를 방문한다. 그리고 정점 2와 인접한 정점 3의 degree를 1 줄이면 degree가 0이 된 정점 3을 방문할 수 있게 된다.
이 문제에서는 이를 이용해 문제를 해결해 보도록 하자. 우선 각 정점의 degree를 저장할 배열 deg를 정의하고 모든 값을 0으로 초기화한다. 그리고 간선들이 주어질 때 만약 (u, v)라는 간선이 주어지면 u를 방문해야 v를 방문할 수 있으므로 v의 degree를 1 증가시킨다. 간선들을 모두 입력받은 뒤 degree가 0인 정점들을 queue에 넣는다.
이 문제에서 구하고자 하는 것은 어떤 정점을 방문해 건물을 건설하는데 걸리는 최소 시간인데, 이를 구하기 위해서는 이 정점을 방문하기 위해 방문한 다른 정점들 중 가장 오래 걸린 시간을 골라 해당 정점의 시간을 더해야 한다. 왜냐하면 건물은 동시에 짓는 것이 가능하기에, 최대한 오래 걸리는 건물을 먼저 짓고 그 사이에 다른 건물을 짓는 것이 효율적이기 때문이다. 예를 들어 건물 2와 건물 3을 지어야 건물 4를 지을 수 있다고 할 때 건물 2가 10초 건물 3이 100초가 걸린다고 하면 건물 4를 지을 수 있을 조건을 만족하는 최소의 시간은 100초가 된다. 왜냐하면 건물 3을 무조건 지어야 하므로 최소 100초가 걸리는데, 만약 건물 2를 먼저 짓고 그 다음에 건물 3을 지으면 건물 2를 먼저 지은 시간만큼 시간이 낭비되기 때문이다. 그러므로 제일 오래 걸리는 건물 3을 먼저 짓고 그 사이에 건물 2를 지으면 효율적으로 시간을 사용할 수 있다.
그런데 이를 계산하려면 결국 해당 정점을 방문하기 위한 정점 각각에 대해 건물을 건설하는데 걸리는 시간을 계산해야 하는데, 이를 미리 저장하지 않고 계산하면 매번 부분 문제를 해결할 때마다 이 시간을 계산해야 한다. 그러므로 dynamic programming을 이용해 계산 결과를 미리 배열에 저장해 두고 필요할 때 배열에서 꺼내 쓸 수 있도록 한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
D = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
# 각 정점의 degree를 저장하는 배열
deg = [0 for _ in range(N+1)]
queue = deque()
for _ in range(K):
X, Y = map(int, input().split())
graph[X].append(Y)
# (X, Y) 간선이 있는 경우 Y의 degree를 1 증가시킨다.
deg[Y] += 1
# degree가 0인 정점을 queue에 추가한다.
for i in range(1, N+1):
if deg[i] == 0:
queue.append(i)
W = int(input())
# 각 정점에 건물을 건설하는데 걸리는 최소 시간을 저장하는 배열
dp = [D[i] for i in range(N+1)]
while queue:
u = queue.popleft()
for v in graph[u]:
deg[v] -= 1
# 각 정점을 방문하기 위한 정점들 중 가장 오래 걸리는 시간을 골라
# 결과적으로 가장 효율적으로 건설 시간을 사용하는 경우를 선택한다.
dp[v] = max(dp[u] + D[v], dp[v])
# degree가 0이 된 정점은 방문 가능하므로 queue에 추가한다.
if deg[v] == 0:
queue.append(v)
print(dp[W])