[백준] 2056번 : 작업

2056번: 작업

2056번: 작업

🤔 문제분석

위상정렬을 알고 있다면 해당문제를 쉽게 풀 수 있다. 위상정렬을 간단하게 설명하자면, 진입차수를 입력받아 진입차수가 0일때만 방문하도록한다. 여기서 방문할때에 기존에 걸렸던 시간중 가장 큰 시간을 가져와서 가중치에 더하면 된다.

문제에서 선행관계에 있는 작업이 하나도 없는 작업이 하나 이상 존재함으로 처음 루트를 방문 할때에 진입차수가 0인 루트가 여러개가 있다는 말임으로, 초기 진입차수가 0인 루트를 찾아서 모두 방문 해주어야한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
in_degree = [0 for _ in range(N)]
edge = [[] for _ in range(N)]
time = [0 for _ in range(N)]
dp = [-1 for _ in range(N)]

def dfs(node):
    for child in edge[node]:
        in_degree[child] -= 1
        dp[child] = max(dp[child], dp[node]+time[child])
        if in_degree[child] <= 0:
            dfs(child)
            
def get_roots():
    roots = []
    for n in range(N):
        if in_degree[n] == 0:
            roots.append(n)
            
    return roots

for i in range(N):
    temp = list(map(int, input().split()))
    time[i] = temp[0]
    in_degree[i] = temp[1]
    if temp[1]:
        for n in temp[2:]:
            edge[n-1].append(i)

roots = get_roots()
for root in roots:
    dp[root] = time[root]
    dfs(root)

print(max(dp))

🎯 피드백 및 개선사항

위상정렬의 내용을 알고 있다면 문제를 쉽게 풀 수 있을 것이라고 생각됩니다.