[알고리즘][Python] 백준 1005 ACM Craft 문제 풀이

문제 출처 : www.acmicpc.net/problem/1005

1005번: ACM Craft

---

문제 해석 : 원하는 건물을 지을 수 있을 때까지 얼마나 시간이 걸리는지 구하는 문제이다.

 

문제 풀이 : 위상 정렬과 DP를 활용해서 문제를 풀이 할 수 있다.

- 진입 차수를 이용해서 위상 정렬로 차례로 건물을 건설한다.

- 진입 차수가 0이 되어 추가될때 DP 테이블에 현재 자신의 테이블과 이전과 지금을 합한것을 비교하여 큰 것을 저장한다.

---

풀이 코드

from collections import defaultdict, deque

def topology_sort():
    DP_table = [0] * (N+1)

    q = deque()

    for i in range(1, N+1):
        if in_degree[i] == 0:
            q.append(i)
            DP_table[i] += time_list[i]

    while q:
        now = q.popleft()

        for i in graph[now]:
            in_degree[i] -= 1
            DP_table[i] = max(DP_table[i], DP_table[now] + time_list[i])

            if in_degree[i] == 0:
                q.append(i)


    return DP_table[target]
    
    
T = int(input())

for test_case in range(T):

    N, K = map(int, input().split())
    time_list = [0] + list(map(int, input().split()))
    graph = [[] for _ in range(N+1)]
    in_degree = [0] * (N+1)

    for _ in range(K):
        start, end = map(int, input().split())
        graph[start].append(end)
        in_degree[end] += 1

    target = int(input())

    print(topology_sort())

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.