BOJ 1516 - 게임 개발 링크
(2022.11.08 기준 G3)
(치팅하면 영원히 개발 회사에 갇힘)

문제

각 건물마다의 건설 시간과 건물 건설 순서가 주어질 때, 모든 건물의 완공 최소 시간 출력

알고리즘

건물 간 순서가 있으며 모든 건물을 짓기 가능하니깐, 건물들은 DAG를 이룬다. 그러므로 위상 정렬 및 위상 정렬 순서에 따른 DP로 시간을 구해야 한다.

풀이

위와 같은 건물 순서와 짓는 시간이 있다면 저렇게 구해진다.
간단하게 말하면, 어떤 건물 i번의 총 완공 시간은 (건물 i번의 짓는 시간 + max(i번으로 진입하는 건물들의 총 완공 시간)) 이다.

건물 순서에 따른 그래프와 진입 차수를 구해놓고, 진입 차수가 0인 건물 번호로 하여금 위상 정렬을 시작하면 된다. 그리고 건물이 뽑힐 때마다 건물 짓는 시간을 더해주고, 다음 건물 완공 시간에는 현재 건물 완공 시간과 비교하여 더 큰 값으로 저장하면 된다.

코드

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

def solve():
    N = int(input())
    build = [0] * (N + 1) # 짓는 시간
    graph = [[] for _ in range(N + 1)] # 건물 순서
    ind = [0] * (N + 1) # 진입차수

    for i in range(1, N + 1):
        time, *lst = map(int, input().split()) # 짓는 시간과 먼저 지어야 하는 건물들
        build[i] = time
        for j in lst[:-1]: # 마지막은 -1이므로 제외
            graph[j].append(i)
            ind[i] += 1

    # 진입차수가 0인 정점은 곧 DAG의 시작
    queue = deque()
    for i in range(1, N + 1):
        if not ind[i]:
            queue.append(i)

    dp = [0] * (N + 1) # 각 건물들의 완공 최소 시간
    while queue:
        i = queue.popleft()
        dp[i] += build[i] # 먼저 지어져야 하는 건물들이 완공이 되었으므로 이 건물을 짓자.
        for j in graph[i]:
            dp[j] = max(dp[i], dp[j]) # j 건물로 진입하는 건물들의 완공 시간의 최대가 j 건물이 지어지는 시작 시간이 된다.
            ind[j] -= 1
            if not ind[j]: # j 건물을 위해 지어져야 하는 건물들이 전부 지어졌으면 j를 짓자.
                queue.append(j)

    # 1번 건물부터 차례대로 완공 시간 출력
    for i in range(1, N + 1):
        print(dp[i])

solve()

여담

ACM Craft와 거의 같은 문제다.
1+1 수준..?