[BOJ 1516] 게임 개발

• 출처: BOJ 1516
• 분류: 위상 정렬 · Gold III

문제

N개의 건물이 있고, 각 건물은 짓는 데 시간이 걸린다. 일부 건물은 선행 건물을 먼저 지어야 한다. 여러 건물을 동시에 지을 수 있을 때, 각 건물의 최소 완성 시간을 구한다.

핵심

선행 조건이 있는 작업 스케줄링 → 위상 정렬 + DP. 위상 순서대로 처리하면서 dp[v] = max(dp[u] + build[v]) (모든 선행 u)로 완성 시간을 전파한다.

풀이

import sys
from collections import deque

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

build = [0] * (N + 1)
g = [[] for _ in range(N + 1)]
indeg = [0] * (N + 1)

for i in range(1, N + 1):
    line = list(map(int, input().split()))
    build[i] = line[0]
    for pre in line[1:-1]:
        g[pre].append(i)
        indeg[i] += 1

dp = build[:]

q = deque()
for i in range(1, N + 1):
    if indeg[i] == 0:
        q.append(i)

while q:
    u = q.popleft()
    for v in g[u]:
        dp[v] = max(dp[v], dp[u] + build[v])
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

print("\n".join(map(str, dp[1:])))

메모

• 위상 정렬이란
  • DAG(유향 비순환 그래프)에서 간선 방향을 거스르지 않는 순서로 노드를 나열하는 것이다
  • 진입 차수(indegree)가 0인 노드부터 큐에 넣고, 꺼낼 때마다 후속 노드의 진입 차수를 줄인다. 0이 되면 큐에 넣는다
  • 이 순서가 “선행 조건을 모두 만족한 뒤 처리”를 보장한다
• DP 전파
  • dp[i]는 건물 i가 완성되는 최소 시간이다
  • 선행 건물이 없으면 dp[i] = build[i] (자기 건설 시간)
  • 선행 건물 u가 있으면 dp[v] = max(dp[v], dp[u] + build[v]). 모든 선행 건물 중 가장 늦게 끝나는 것이 병목이다
  • 여러 건물을 동시에 지을 수 있으므로, 병렬 경로 중 최대값이 답이다
• 입력 처리
  • 각 줄의 마지막 값은 -1 (종료 표시)이므로 line[1:-1]로 선행 건물 번호만 추출한다
• 이 패턴의 다른 이름
  • Critical Path Method (CPM): 프로젝트 관리에서 선행 작업이 있는 일정의 최소 완료 시간을 구하는 기법
  • DAG DP: DAG 위에서 위상 순서로 DP를 돌리는 일반적인 패턴

복잡도

풀이	시간	공간
위상 정렬 + DP	O(V + E)	O(V + E)