[백준] 1516번 - 게임 개발

---

문제 분석

사이클이 없는 방향그래프에서 순서를 찾는 문제이므로 위상정렬을 통해 해결할 수 있다. 이 문제를 푸는과정에서 주의해야 할 점은 다음 예와 같다.
1노드 15초, 2노드 13초 3노드는 1노드와 2노드가 지어진 후 지을 수 있다고 할때,
일반적인 큐를 이용해서 진입차수를 판단하는 경우에는 13초 + 3노드를 짓는수가 될 것이다. 그러나 실제로는 15초 + 3노드를 짓는 만큼의 시간이 걸린다. 따라서 각 건물을 노드로 보고 해당 노드를 짓기 전까지 필요한 시간의 값을 파악한 후 그 값을 해당 노드를 지을때 더해주면 된다.

---

소스 코드

# 게임 개발

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
arr = [[] for _ in range(N + 1)]
time = [0 for _ in range(N + 1)]
beforeTime = [0 for _ in range(N + 1)]
getPointed = [0 for _ in range(N + 1)]
queue = deque()

for i in range(1, N + 1):
    values = list(map(int, input().split()))
    time[i] = values[0]
    values = values[1:]
    for v in values:
        if v == -1:
            break
        arr[v].append(i)
        getPointed[i] += 1

for i in range(1, N + 1):
    if getPointed[i] == 0:
        beforeTime[i] = time[i]
        queue.append(i)

while queue:
    node = queue.popleft()
    for value in arr[node]:
        getPointed[value] -= 1
        beforeTime[value] = max(beforeTime[value], beforeTime[node])
        if getPointed[value] == 0:
            time[value] += beforeTime[value]
            beforeTime[value] = time[value]
            queue.append(value)

for value in time[1:]:
    print(value)