[백준] ACM Craft 1005번 (python) 위상정렬 + dp

출처 : https://www.acmicpc.net/problem/1005

 

풀이 방법 

위 문제는 그래프에서 작업의 우선순위가 정해져 있으므로, 위상 정렬을 사용해 해결할 수 있다.

위상 정렬에 dp알고리즘을 추가하여 현재 노드를 완료하기 위한 시간을 계산할 수 있다.

 

from collections import deque

def topological_sort(N, K, cTime, linked, degree, win_num): 위상정렬
    dp = [0] * (N + 1)
    queue = deque()

    # 시작 점 초기화
    for i in range(1, N + 1):
        if degree[i] == 0:
            queue.append(i)
            dp[i] = cTime[i - 1]

    # 위상 정렬 수행
    while queue:
        now = queue.popleft()
        for next in linked[now]: ## 연결된 노드 끊어주기
            degree[next] -= 1
            dp[next] = max(dp[next], cTime[next - 1] + dp[now]) ## 이전의 노드에서 온 시간, 현재 노드에서 온 시간 비교
            if degree[next] == 0:
                queue.append(next)

    return dp[win_num] ## 승리하는 건물의 시간 계산

def process_case():
    N, K = map(int, input().split())  # 건물 수, 규칙 수
    cTime = list(map(int, input().split()))  # 건설 시간 입력 받기
    degree = [0] * (N + 1)  # degree 초기화
    linked = [[] for _ in range(N + 1)]  # 그래프 초기화

    for _ in range(K):
        a, b = map(int, input().split())  # 연결
        degree[b] += 1
        linked[a].append(b)

    win_num = int(input())  # 목표 건물 번호
    result = topological_sort(N, K, cTime, linked, degree, win_num)
    print(result)

def main():
    T = int(input())  # 테스트 케이스 수
    for _ in range(T):
        process_case()

main()