BOJ 1516 게임 개발

https://www.acmicpc.net/problem/1516
시간 2초, 메모리 128MB
input :

• N(1 ≤ N ≤ 500)
• 걸리는 시간, 건물을 짓기 위해 먼저 지어져야 하는 건물의 번호.
• 각 줄은 -1로 끝난다

output :

• N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력

조건 :

• 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에
• 여러 개의 건물을 동시에 지을 수 있다.

---

1. 일단 건물을 짓는데에 순서가 존재한다.
   건물을 짓는데에 순서가 존재하니까 위상 정렬을 해야 한다고 볼 수 있다.
   차수가 없는 놈들을 찾아서 이 넘들이 갈 수 있는 노드들을 찾고.
   그 위치에서 업데이트를 해주자.
   ans변수에는 모든 노드들에 대해 각 건물이 시간을 얼마나 잡아먹는지를 저장하자.

2. 조건에서 봤듯이 여러 건물을 동시에 지을 수 있기 때문에 건물들 중 가장 오래 걸리는 건물을 찾아야 한다.
   ans 변수에 각 건물이 건설되는데 걸리는 최소 시간을 저장 할 건데. 여러 건물을 동시에 지을 수 있으니까 여러 건물들의 건설시간을 비교해서 이 중 가장 큰 값이 최소 시간이 될것이다.

-> 가장 큰 걸로 정해 놓으면 그거 보다 적게 걸리는 애들은 동시에 지어서 이미 건설 완료했을 테니까.

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
degree = [0] * (n + 1)
data = [0] * (n + 1)
ans = [0] * (n + 1)
q = deque()

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))

    data[i + 1] = temp[0]

    # 본인에게 들어오는 간선이 없음. 위상정렬의 시작점
    if len(temp) == 2:
        q.append(i + 1)
        # 다른 건물들 지을 필요 없으니까 ans 변수에 저장해주자.
        ans[i + 1] = temp[0]
        continue

    # temp 값에 들어있는 Node에서 i + 1번 노드로 들어오는 간선을 입력받는 것.
    for j in range(1, len(temp) - 1):
        # start = temp[j]
        graph[temp[j]].append(i + 1)
        degree[i + 1] += 1

while q:
    now = q.popleft()

    for next_node in graph[now]:
        degree[next_node] -= 1
        # 현재 노드의 건물을 지은 후에 next_node 건물을 짓는데에 걸리는 시간이 
        # 원래 있던 ans[next_node]가 더큰지 아니면 지금 ans[now]를 지은 후에 next_node건물을 짓는 것이
        # 더 오래 걸리는 지를 비교 한다.
        ans[next_node] = max(ans[next_node], data[next_node] + ans[now])

        if degree[next_node] == 0:
            q.append(next_node)

for i in range(1, n + 1):
    print(ans[i])