[BOJ] 1005 ACM Craft | Python

문제

백준 1005번 ACM Craft | 골드3

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

1005번: ACM Craft

• 알고리즘 분류 : 다이나믹 프로그래밍(DP) | 그래프 이론 | 위상 정렬

 

 

 

풀이 과정

파이썬 풀이

import sys
input = sys.stdin.readline
from collections import deque

def topology():
    q = deque()
    for k in range(1, N+1):
        # 진입차수 == 0이라면 작업 가능 
        if not in_degree[k]:
            q.append(k)
            dp[k] = times[k]

    while q:
        now = q.popleft()
        # now가 끝났으므로
        # now가 끝난 뒤 할 수 있는 일들에 대해 진입차수 1씩 감소시키기
        for next in graph[now]:
            in_degree[next] -= 1
            if not in_degree[next]:
                q.append(next)
            # now가 끝난 뒤 next를 수행한 시간과, 이미 저장되어 있는 next 시간 중 최대값 저장
            # 선행작업이 모두 끝난 후에 작업이 가능하기 때문에 최대값 저장 
            dp[next] = max(dp[next], dp[now]+times[next])
            
            ## 진입차수가 0이 되었을 때만 비교한다면
            ## next의 진입차수가 0이 되지 않았을 때의 now값이랑 비교를 못함
            ## ex) 2, 3 다음 4인데 now == 2일 때 값 갱신 안 됨

T = int(input())
for tc in range(T):
    N, K = map(int, input().split())
    times = [0] + list(map(int, input().split()))
    graph = [[] for _ in range(N+1)]  # 선행 작업 기록
    dp = [0] * (N+1)
    in_degree = [0] * (N+1)   # 진입차수

    for k in range(K):
        x, y = map(int, input().split())
        graph[x].append(y)
        in_degree[y] += 1

    topology()
    W = int(input())
    print(dp[W])

• 위상정렬도, dp도 익숙하지 않은 상황에서 풀었던 문제라 완전히 이해하는데 시간이 조금 걸렸었다.
• 백준 2056번 작업 문제와 유사한 문제이다. 해당 문제의 풀이는 아래 링크 참조

https://eunjng.tistory.com/25

[BOJ] 2056 | 작업 | Python