작업 (위상정렬)

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

 

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

 

예제 입력 1

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

예제 출력 1

23

 

- 문제 해결

이미지 상에서 노드를 다 그리지 않은 것은 같은 것을 중복해서 체크하는 과정이 너무 많아서 4번 단계까지의 흐름만 나타냈습니다.

 

첫 아이디어는 이랬다.. 근데 이렇게 풀다보니 dfs로 풀면서 다시 시간을 체크해서 7번작업이 끝났을 때 최소값 찾는 과정이 정말 너무 중복도 많고 불필요한 과정을 너무 많이 반복한다는 생각이 들어 다른 방법으로 풀어보자는 생각이 들었다.

위 방식은 기존과 생각은 비슷한데 dfs에서 bfs로 바꾸니 시간단위로 체크해 최대깊이일 때의 최댓값을 정확하게 뽑아내며 더욱 간단하게 이해할 수 있고 반복도 많이 줄었다.

from collections import deque

n = int(input())
time = [0] * (n + 1)
next_work = {i: [] for i in range(1, n + 1)}
indegree = [0] * (n + 1)
dp = [0] * (n + 1)


for idx in range(n):
    work = list(map(int, input().split()))
    t = work[0]
    adv_cnt = work[1]
    indegree[idx + 1] = adv_cnt
    for i in range(2, 2 + adv_cnt):
        next_work[work[i]].append(idx + 1)

    time[idx + 1] = t

queue = deque()

for i in range(1, n + 1):
    if indegree[i] == 0:
        queue.append(i)
        dp[i] = time[i]

while queue:
    cur = queue.popleft()

    for nxt in next_work[cur]:
        dp[nxt] = max(dp[nxt], dp[cur] + time[nxt])
        indegree[nxt] -= 1

        if indegree[nxt] == 0:
            queue.append(nxt)

print(max(dp))