[알고리즘][Python] 백준 2056 작업 문제 풀이

문제 출처 : www.acmicpc.net/problem/2056

2056번: 작업

---

문제 해석 : 작업에 우선 순위가 정해져 있고 우선순위를 모두 완수 해야 다음 작업을 할 수 있다. 다만 작업들은 동시에 수행 가능하다. 이때 모든 작업을 완료하는데 소요되는 시간을 출력하라

 

문제 풀이 :  위상정렬, 다이나믹프로그래밍을 통해서 문제를 풀이 할 수 있다. 진입 차수가 0인 것을 큐에 넣으면서 dp 테이블을 수정한다.

점화식을 다음과 같다.

- dp[x] = max(dp[x], work_time[x] + dp[x-1])

- 즉 자신의 우선순위에 있는 작업 중에 가장 오래 걸리는 작업에 자신의 작업시간을 더한 값이다.

- 모든 작업이 완료되는 것은 작업 시간 중에 가장 오래 걸리는 것이 완료 되었을 때이다. 

 

풀이 시간 : 25분 13초

---

풀이 코드

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

N = int(input())

dp_table = [0] * (N + 1)
degree = [0] * (N + 1)
dependency = defaultdict(list)
work_time = [0] * (N + 1)

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

    work_time[i] = S[0]
    degree[i] = S[1]
    for element in S[2:]:
        dependency[element].append(i)

Q = deque()

for i in range(1, len(degree)):
    if degree[i] == 0:
        Q.append(i)
        dp_table[i] = work_time[i]

while Q:
    now = Q.popleft()
    for element in dependency[now]:
        degree[element] -= 1
        dp_table[element] = max(dp_table[element], dp_table[now] + work_time[element])
        if degree[element] == 0:
            Q.append(element)

print(max(dp_table))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.