BOJ - 1516 - 게임 개발

Updated:

import sys
from collections import deque

def solution():
    N = int(sys.stdin.readline())
    graph = [[] for _ in range(N + 1)]
    degree = [0] * (N + 1)
    dp = [0 for _ in range(N + 1)]
    time = [0 for _ in range(N + 1)]
    dq = deque()
    for idx in range(1, N+1):
        building = list(map(int, sys.stdin.readline().split()))
        time[idx] = building[0]

        for jdx in range(1, len(building) - 1):
            graph[building[jdx]].append(idx)
            degree[idx] += 1

    for i in range(1, N + 1):
        if degree[i] == 0:
            dq.append(i)
            dp[i] = time[i]

    while dq:
        index = dq.popleft()
        for j in graph[index]:
            degree[j] -= 1
            dp[j] = max(dp[index] + time[j], dp[j])
            if degree[j] == 0:
                dq.append(j)

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

https://www.acmicpc.net/problem/1516

Categories:

Updated:

Leave a comment