백준 2056 [작업] 파이썬

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

 

#백준 2056 작업
import sys
from collections import deque
input = sys.stdin.readline

# 작업 개수
N = int(input())

# works[a] : 작업 a를 선행 작업으로 가지는 다음 작업들의 리스트
works = [[] for _ in range(N+1)]

# in_degree[i] : 작업 i의 선행 작업 개수(진입 차수)
in_degree = [0 for _ in range(N+1)]

# need_times[i] : 작업 i 자체를 수행하는 데 걸리는 시간
need_times = [0 for _ in range(N+1)]

# spend_times[i] : 작업 i를 완료하기까지 걸리는 누적 시간 (DP)
spend_times = [0 for _ in range(N+1)]

# 위상정렬을 위한 큐
q = deque()

# 입력 처리
for i in range(1, N+1):
    prev_works = list(map(int, input().split()))

    # 첫 번째 값: 작업 i의 소요 시간
    need_times[i] = prev_works.pop(0)

    # 초기에는 자기 작업 시간만큼만 누적 시간 설정
    spend_times[i] = need_times[i]

    # 두 번째 값: 선행 작업 개수
    prev_work_cnt = prev_works.pop(0)

    # 남은 값들은 선행 작업 번호
    for prev_work in prev_works:
        works[prev_work].append(i)  # prev_work → i
        in_degree[i] += 1           # i의 진입 차수 증가

# 진입 차수가 0인 작업(선행 작업이 없는 작업)을 큐에 넣기
for i in range(1, N+1):
    if in_degree[i] == 0:
        q.append(i)

# 위상정렬 수행
while q:
    curr_work = q.popleft()

    # 현재 작업 이후에 수행 가능한 작업들 확인
    for next_work in works[curr_work]:
        # 진입 차수 감소
        in_degree[next_work] -= 1

        # DP: 다음 작업의 완료 시간 = max(현재 저장된 값, 현재 작업 완료시간 + 다음 작업 소요 시간)
        spend_times[next_work] = max(
            spend_times[next_work],
            spend_times[curr_work] + need_times[next_work]
        )

        # 더 이상 선행 작업이 없으면 큐에 추가
        if in_degree[next_work] == 0:
            q.append(next_work)

# 모든 작업 중에서 가장 오래 걸리는 시간 출력
print(max(spend_times))

# 디버깅용
# print(spend_times)

위상정렬이 조금 익숙해진다.