[BOJ] 2056 작업 | Python

문제

백준 2056번 작업 | 골드4

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

2056번: 작업

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

 

 

 

풀이 과정

파이썬 풀이

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

N = int(input())
in_degree = [0] * (N+1) # 진입차수(선행작업의 개수)
graph = [[] for _ in range(N+1)] # 선행작업 기록
times = [0] * (N+1) # 소요 시간
dp = [0] * (N+1)

for n in range(N):
    t, num, *args = map(int, input().split())
    times[n+1] = t
    # 선행 작업이 있다면 
    if num:
        for a in args:
        	# (n+1)번째 작업의 선행작업이 a 
            # a 다음에 할 수 있는 일 탐색하도록 graph의 a번째에 이후 작업을 추가
            graph[a].append(n+1)
            # n+1의 진입차수 증가시키기 
            in_degree[n+1] += 1

def topology():
    q = deque()
    for p in range(1, N+1):
    	# 진입차수 == 0이라면 작업 가능 
        if not in_degree[p]:
            q.append(p)
            dp[p] = times[p]
    while q:
        now = q.popleft()
        # now가 끝났으므로
        # now가 끝난 뒤 할 수 있는 일들에 대해 진입차수 1씩 감소시키기
        for next in graph[now]:
            in_degree[next] -= 1
            # next의 진입차수가 0이 되면 작업 가능 -> q에 추가
            if not in_degree[next]:
                q.append(next)
            dp[next] = max(dp[next], dp[now]+times[next])
            # now가 끝난 뒤 next를 수행한 시간과, 이미 저장되어 있는 next 시간 중 최대값 저장
            # 선행작업이 모두 끝난 후에 작업이 가능하기 때문에 최대값 저장 

topology()
print(max(dp))

• 선행작업의 개수가 모두 다르기 때문에 *args를 통해 입력 받았다.
• graph에 저장하는 방식이 조금 다른 것 빼고는 백준 1005번 ACM Craft와 흡사한 문제 같다.
  해당 문제의 풀이는 아래 링크 참조

https://eunjng.tistory.com/26

[BOJ] 1005 | ACM Craft | Python