백준 2056번 : 작업 in Python

2056번: 작업

 

www.acmicpc.net

이 문제는 수행해야 할 작업과 각 작업마다 걸리는 시간이 주어질 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제이다. 단, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

이 문제는 이전의 ACM Craft 문제와 유사한 문제이나, 목표 정점에 도달하는데 걸리는 시간을 구하는 ACM Craft 문제와 달리, 모든 작업을 끝내는데 걸리는 시간을 구한다는 점에서 약간의 차이가 있다. 나머지는 ACM Craft 문제와 거의 같다. 

백준 1005번 : ACM Craft in Python

1005번: ACM Craft www.acmicpc.net 이 문제는 위상 정렬 문제를 좀더 발전시킨 문제로, 위상 정렬을 통한 그래프 탐색에서 목표 정점까지 도달하는데 걸리는 시간의 최소값을 구해야 하는 문제이다. 이전의 줄 세..

wanna-be-developer-yjh.tistory.com

따라서 ACM Craft처럼 위상 정렬과 dynamic programming을 적절히 활용해 각 작업을 완료하는데 걸리는 시간을 구한 뒤, 작업에 끝내는데 걸린 시간 중 가장 긴 시간을 출력하면 된다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N = int(input())
graph = [[] for _ in range(N+1)]
time = [0 for _ in range(N+1)]
deg = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for i in range(1, N+1):
    arr = list(map(int, input().split()))
    time[i] = arr[0]
    m = arr[1]
    for j in range(2, m+2):
        graph[arr[j]].append(i)
        deg[i] += 1
queue = deque()
dp = [0 for _ in range(N+1)]
for i in range(1, N+1):
    if deg[i] == 0:
        queue.append(i)
        dp[i] = time[i]
while queue:
    u = queue.pop()
    for v in graph[u]:
        dp[v] = max(dp[v], dp[u] + time[v])
        deg[v] -= 1
        if deg[v] == 0:
            queue.append(v)
print(max(dp))