🦊 작업

1. 문제 링크

2056번: 작업

2. 코드

Pypy3 136904KB 632ms

N = int(input())

workflow = [] # 다음노드
pre_workflow = [] # 선행노드
in_degree = [0] * N # 진입차수
visit = [0] * N # 방문
time = []
for i in range(N):
    workflow.append([])
    pre_workflow.append([])

for i in range(N):
    work = list(map(int, input().split()))

    # 걸리는 시간
    time.append(work[0])
    # 선행 작업 연결
    for j in range(work[1]):
        pre_work = work[2 + j]
        # 다음에 진행해야하는 간선 연결
        workflow[pre_work - 1].append(i)
        in_degree[i] += 1
        # 선행 작업으로부터 들어오는 간선 연결
        pre_workflow[i].append(pre_work - 1)

# 현재 작업까지 소요된 총 시간
dp = [0] * 10001

# 위상정렬 큐
q = [0]
visit[0] = 1
total_time = 0
while q:
    cur = q.pop(0)

    # 진입 노드들의 시간을 기반으로 현재 시간을 지정
    pre_time = 0
    for i in range(len(pre_workflow[cur])):
        pre_time = max(pre_time, dp[pre_workflow[cur][i]])
    dp[cur] = pre_time + time[cur]
    total_time = max(total_time, dp[cur])

    # 다음 노드의 진입 차수를 제거
    for i in range(len(workflow[cur])):
        node = workflow[cur][i]
        in_degree[node] -= 1

    # 진입 차수가 0인 노드 큐에 삽입
    for i in range(N):
        if not visit[i] and in_degree[i] == 0:
            q.append(i)
            visit[i] = 1

print(total_time)

3. 해설

모든 노드의 진입노드, 진출노드를 기록하여 위상정렬 수행 위상 정렬 과정에서 진입 노드들의 최댓값을 가져와 선행 작업이 모두 끝나는 시간 가져옴 그 시간 + 현재 작업의 시간으로 걸리는 시간의 합을 구함