ACM Craft ( 1005번 )

1005번: ACM Craft

 

🧠 알고리즘

위상 정렬을 활용한 DP (동적 계획법) 문제를 해결하는 알고리즘

위상 정렬 + 누적 비용 계산
큐에 루트 노드를 넣고, 자식 노드로 진행하면서 누적 최대 비용을 갱신함.

 

🧾 코드

import sys
from collections import deque

def _mk_graph(n, k):
    graph_c, graph_p = {}, {}
    for i in range(1, n + 1):
        graph_c[i] = []
        graph_p[i] = 0

    for _ in range(k):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph_c[a].append(b)
        graph_p[b] += 1

    return graph_c, graph_p

    
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().rstrip().split())
    n_list = list(map(int, sys.stdin.readline().rstrip().split()))
    graph_c, graph_p = _mk_graph(n, k)
    cost_list = [0] * n

    queue = deque()
    for k, v in graph_p.items():
        if v == 0: # 루트인 경우
            queue.append(k)
            cost_list[k - 1] = n_list[k - 1]

    while queue:
        now_q = queue.popleft()
        for n_q in graph_c[now_q]:
            cost_list[n_q - 1] = max(cost_list[n_q - 1], cost_list[now_q - 1] + n_list[n_q - 1])
            graph_p[n_q] -= 1
            if graph_p[n_q] == 0:
                queue.append(n_q)

    target = int(sys.stdin.readline().rstrip())
    print(cost_list[target - 1])

 

⏱️ 시간 복잡도

각 노드 및 간선을 한 번씩 탐색 하므로 : 선형 시간

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )