작업

출처 : 백준 #2056

시간 제한	메모리 제한
2초	256MB

---

문제

수행해야 할 작업 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

---

풀이

생각

• 우선 time이라는 변수에 해당 노드에서 수행하는 최종 시간을 기입하였다.
• pre 변수를 통해 선행하는 노드의 번호를 리스트 형태로 기록하였다.
• for 문을 돌면서 선행 노드까지의 수행 시간 중 가장 최대 시간을 temp에 기록하고 현재 time의 시간에 더하여 update 해주었다.
• 그리고 마지막으로 max함수를 통해 최종 시간이 가장 오래 걸리는 노드의 값을 도출해 냈다.
  

python code

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

n = int(input())
time = [0]*(n+1)                # 해당 노드에서 걸리는 시간
pre = [[] for _ in range(n+1)]  # 선행해야하는 노드 번호들

for i in range(1, n+1):
    temp = list(map(int, input().split()))
    time[i] = temp[0]
    if temp[1] != 0:
        pre[i] = temp[2:]

for i in range(1, n+1):
    temp = 0   
    for j in pre[i]:    # 선행작업이 존재하는 경우
        temp = max(temp, time[j])
    time[i] += temp
print(max(time))