본문 바로가기

알고리즘/백준

[백준] 1005번 : ACM Craft

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