728x90
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
해당 문제는 깊이우선탐색 + 다이나믹프로그래밍 으로 문제를 해결 하였습니다.
1. end_nodes를 찾습니다. end_nodes는 루트 노드들 입니다.
2. end_nodes로 부터 시작하여 dp 테이블을 업데이트 합니다. ( 방문 가능한 노드들중 최대값으로 )
3. dp[W] 값을 출력하여 W의 최대값을 출력합니다.
T = int(input())
def dfs(node, graph, d, dp):
if dp[node] != -1:
return dp[node]
max_time = 0
for prev_node in graph[node]:
max_time = max(max_time, dfs(prev_node, graph, d, dp))
dp[node] = max_time + d[node]
return dp[node]
for _ in range(T):
N, K = map(int, input().split())
d = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)
for _ in range(K):
X, Y = map(int, input().split())
graph[Y].append(X)
in_degree[X] += 1
W = int(input())
dp = [-1] * (N + 1)
end_nodes = [node for node in range(1, N + 1) if in_degree[node] == 0]
for node in end_nodes:
dfs(node, graph, d, dp)
print(dp[W])
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1062번 : 가르침 (0) | 2023.10.15 |
---|---|
[백준] 3055번 : 탈출 (0) | 2023.08.31 |
[백준] 2146번 : 다리 만들기 (0) | 2023.08.30 |
[백준] 2638번 : 치즈 (0) | 2023.08.25 |
[백준] 13023번 : ABCDE (0) | 2023.08.25 |