[Python] 백준 2056 작업

2056번: 작업

위상정렬 마스터를 해야지 이런 느낌으로 위상정렬 문제만 풀고있다. 전체적으로는 비슷한 문제여서 백준 티어 경험치작을 하고싶다면 위상정렬 문제를 푸는게 어떨까 추천한다. 어차피 티어는 자기만족이니깐..

 

위상정렬 : DP를 사용해서 작업시간을 업데이트 시켜준다. 주의할 점은 작업이 가장 오래걸린 것을 출력해야한다. 1로 출발해서 N으로 끝나는 작업이 예시로 들어왔지만, 그렇지 않은 경우도 있기 때문에 max값을 출력해주면 된다. 

 

전체코드

import sys
import collections

input = sys.stdin.readline

N = int(input())
times = [0 for _ in range(N + 1)]
inDegree = [0 for _ in range(N + 1)]
dp = [0 for _ in range(N + 1)]

graph = collections.defaultdict(list)
for i in range(1, N + 1):
    work = list(map(int, input().split()))
    times[i] = work[0]
    inDegree[i] += work[1]
    for j in work[2:]:
        graph[j].append(i)

queue = collections.deque()
for i in range(1, N + 1):
    if inDegree[i] == 0:
        dp[i] = times[i]
        queue.append(i)

while queue:
    node = queue.popleft()

    for i in graph[node]:
        inDegree[i] -= 1
        dp[i] = max(dp[node] + times[i], dp[i])
        if inDegree[i] == 0:
            queue.append(i)

print(max(dp))