백준|1516번|게임 개발

문제 설명

건물의 건설 시간과 건물을 짓기 위해 필요한 건물의 번호들을 입력받고 각 건물을 짓기 위해 걸리는 시간을 출력하는 문제입니다. 건물은 동시에 여러 개를 지을 수 있습니다.

작동 순서

1. 건물의 개수와 건물을 짓는 데 필요한 시간, 건물을 짓기 전에 지어야 하는 건물의 번호를 입력받습니다.
2. 1을 입력받을 때 현재 건물의 번호를 현재 건물을 짓기 전에 지어야 하는 건물의 하위 건물을 저장하는 그래프에 저장하고 현재 건물의 필요 상위 건물 개수를 +1해 줍니다.
3. 현재 지을 수 있는 건물(필요 상위 건물 개수가 0인 건물)의 번호를 큐에 삽입합니다.
4. 큐에서 순서대로 건물의 번호를 꺼내며 현재 건물을 짓는 데 걸리는 시간을 저장합니다.(해당 건물을 짓는 데 필요한 건물들을 짓는 시간+현재 건물을 짓는 시간)
5. 4번의 과정이 끝나면 현재 건물의 하위 건물 그래프에서 건물들의 필요 상위 건물 수를 -1해 줍니다. 시간을 갱신할 때는 동시에 건물을 짓는 것이 가능하므로 저장되어있는 시간보다 현재 시각이 더 오래 걸리는 경우에만 현재 건물을 짓는데 시간으로 갱신해줍니다.(동시에 건물을 지을 수 있으면 가장 늦게 완성되는 필요 건물이 지어지기 전에 다른 필요건물이 모두 지어질 것이라서 가장 늦게 완성되는 필요건물의 시간만 있으면 됩니다.)
6. 5번의 과정이 끝난 뒤 필요한 건물 수가 0인 건물이 있으면 그 건물의 번호를 큐에 삽입합니다.
7. 모든 연산이 끝나면 건물의 번호대로 필요한 시간을 출력합니다.

소스코드

import sys
from collections import deque

N = int(sys.stdin.readline())

need = [0]*(N+1)
dp = [0]*(N+1)
time = [0]*(N+1)
graph = [[] for _ in range(N+1)]
q = deque()

for i in range(N):
    nums = list(map(int, sys.stdin.readline().split()))
    time[i+1] = nums[0]
    for j in nums[1:-1]:
        graph[j].append(i+1)
        need[i+1] += 1

for i in range(1, len(need)):
    if need[i] == 0:
        q.append(i)

while q:
    num = q.popleft()
    dp[num] += time[num]
    for i in graph[num]:
        if dp[i] < dp[num]:
            dp[i] = dp[num]
        need[i] -= 1
        if need[i] == 0:
            q.append(i)


for i in range(1, N+1):
    print(dp[i])