https://www.acmicpc.net/problem/1005
시간 1초, 메모리 512MB
input :
- 테스트케이스의 개수 T
- 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K
- 각 건물당 건설에 걸리는 시간 D
- 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다)
- 백준이가 승리하기 위해 건설해야 할 건물의 번호 W
output :
- 건물 W를 건설완료 하는데 드는 최소 시간을 출력
문제를 풀려면 어떻게 해야 하는가??
일단 생긴거 부터가 위상정렬을 해야 되게 생겼다.
그래도 혹시나 싶어서 그냥 target에서 부터 역으로 찾아 들어간다면 답을 구할 수 있지 않을 까 했는데
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4
이러한 경우가 존재할 경우에는 레벨 별로 구분을 할 수 없고, 그냥 위상정렬의 순서로 찾아 들어가야 한다.
그리고 하나 또 놓친 것은, 레벨별로 비교를 하려고 하더라도 모든 노드가 꼭 target 노드와 연결되진 않고 연결되지 않아도 그 값을 확인하러 들어 갈 수 있다. 고로 이를 나타내는 방법이 필요한데
그게 뭐가 중요한가 그냥 dp로 다 찾은 다음에 target 인덱스를 출력하면 된다.
모든 경우의 수를 다 확인 하면서 업데이트를 해주자. 그리고 이러한 DAG 에선 visit은 필요가 없지만 진입 차수가 0인지는 확인 해 줘야 한다. 그렇지 않으면 모든 노드를 다 확인 하기 떄문에 시간 초과가 엄청나게 발생한다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n, k = map(int, sys.stdin.readline().split())
data = [0] + list(map(int, sys.stdin.readline().split()))
degree = [0] * (n + 1)
graph = [[] for j in range(n + 1)]
for j in range(k):
x, y = map(int, sys.stdin.readline().split())
degree[y] += 1
graph[x].append(y)
target = int(sys.stdin.readline())
dp = [0] * (n + 1)
q = []
for j in range(1, n + 1):
if degree[j] == 0:
q.append(j)
dp[j] = data[j]
while q:
now = q.pop(0)
for next_node in graph[now]:
degree[next_node] -= 1
dp[next_node] = max(dp[next_node], dp[now] + data[next_node])
if degree[next_node] == 0:
q.append(next_node)
print(dp[target])
