💻 백준 1005번: ACM Craft

문제 소개 🧐

건물을 짓는 순서 규칙과 각 건물의 건설 시간이 주어질 때, 특정 건물이 완성되기까지 걸리는 최소 시간을 구하는 문제다.

  • 각 건물은 건설 시작부터 완성까지 고유의 시간이 걸린다.
  • 특정 건물을 지으려면 선행되어야 할 건물들이 모두 완성되어야 한다.
  • 선행 건물이 여러 개일 경우, 모든 선행 건물이 완성되는 시간 중 가장 늦은 시간을 기준으로 다음 건물 건설이 시작된다.

이는 전형적인 위상 정렬(Topological Sort)과 동적 계획법(DP) 을 응용하는 문제다.

입력 📝

  • 테스트케이스 T
  • 각 테스트케이스마다:
    • 건물의 개수 N, 건설 순서 규칙의 수 K
    • 각 건물의 건설 시간 D1, …, DN
    • K개의 건설 순서 규칙 (X → Y)
    • 최종적으로 건설해야 할 건물의 번호 W

출력 📤

  • 건물 W를 건설 완료하는 데 드는 최소 시간

나의 풀이 ✨

이 문제는 건물의 건설 순서가 방향 그래프(DAG, Directed Acyclic Graph)로 표현될 수 있다. 특정 건물의 최소 건설 완료 시간은 (가장 오래 걸리는 선행 건물의 완료 시간) + (자신의 건설 시간)으로 정의할 수 있다. 이 점화식을 기반으로 DP로 접근했다.

Idea 1: 스택을 이용한 역방향 탐색 및 DP

처음에는 목표 건물 W에서부터 필요한 선행 건물들을 역으로 추적하여 스택에 쌓았다. 그리고 스택을 pop하면서 DP 테이블을 채워나가려고 했다.

dp[i] = max(dp[선행건물1], dp[선행건물2], ...) + d[i]

Code
import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    n, k = map(int, sys.stdin.readline().split())
    d = deque(map(int, sys.stdin.readline().split()))
    d.appendleft(0)
    requirements = [[] for _ in range(n+1)]
    dp = [float('inf')] * (n+1)

    for _ in range(k):  # O(K)
        x, y = map(int, sys.stdin.readline().split())
        requirements[y].append(x)

    w = int(sys.stdin.readline().rstrip())

    for i in range(1, n+1):  # O(n)
        if not requirements[i]:  # 선행 조건으로 필요한 건물이 없는 경우
            dp[i] = d[i]
    
    stack = []
    stack.append(w)

    idx = 0
    while idx < len(stack):  # w 까지 가는 길을 찾음
        child_li = requirements[stack[idx]]
        for child in child_li:
            stack.append(child)
        idx += 1

    while stack:  # w 까지 갈때까지
        cur_node = stack.pop()
        if requirements[cur_node]:
            dp[cur_node] = max(list(map(lambda x: dp[x], requirements[cur_node]))) + d[cur_node]
    
    print(dp[w])
Result: 시간 초과

이 접근 방식의 문제는 스택에서 노드를 꺼내 DP 값을 계산할 때, 해당 노드의 선행 건물들의 DP 값이 아직 계산되지 않았을 수 있다는 점이다. 즉, 위상 정렬 순서를 보장하지 못해 비효율적인 계산이 반복되면서 시간 초과가 발생했다.

Idea 2: 재귀와 메모이제이션을 이용한 Top-Down DP

위상 정렬의 순서를 자연스럽게 보장하는 방법으로 재귀를 이용한 Top-Down 방식을 선택했다. 메모이제이션(Memoization)을 위해 DP 테이블을 사용한다.

  1. get_construct_time(i) 함수를 정의: 건물 i의 최소 건설 완료 시간을 반환한다.
  2. 함수 시작 시, dp[i] 값이 이미 계산되었다면(초기값이 아니라면) 즉시 반환한다. (메모이제이션)
  3. 계산되지 않았다면, 건물 i의 모든 선행 건물 req에 대해 get_construct_time(req)를 재귀적으로 호출하여 가장 오래 걸리는 시간을 찾는다.
  4. dp[i] = (가장 오래 걸리는 선행 건물 시간) + d[i] 점화식을 계산하고 dp 테이블에 저장 후 반환한다.
Code
import sys
from collections import deque

sys.setrecursionlimit(30000)

T = int(sys.stdin.readline().rstrip())

def get_construct_time(i, dp, d, requirements):
    '''
    재귀적으로 top-down으로 건설시간을 구하는 함수
    '''
    if dp[i] != float('inf'):
        return dp[i]
    else:
        max_time = -1
        # 선행 건물이 없는 경우, 자신의 건설시간이 곧 완료시간
        if not requirements[i]:
            max_time = 0
        else:
            for req in requirements[i]:
                time = get_construct_time(req, dp, d, requirements)
                max_time = time if time > max_time else max_time
        
        dp[i] = max_time + d[i]
        return dp[i]

for _ in range(T):
    n, k = map(int, sys.stdin.readline().split())
    d = deque(map(int, sys.stdin.readline().split()))
    d.appendleft(0)
    requirements = [[] for _ in range(n+1)]
    dp = [float('inf')] * (n+1)

    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        requirements[y].append(x)

    w = int(sys.stdin.readline().rstrip())

    # 초기 건물들 시간 설정 (필수는 아님, 재귀 함수에서 처리 가능)
    # for i in range(1, n+1):
    #     if not requirements[i]:
    #         dp[i] = d[i]
    
    get_construct_time(w, dp, d, requirements)
    
    print(dp[w])
Result: 성공! 🎉

재귀 호출을 통해 목표 건물 W에 필요한 선행 건물들의 건설 시간이 자연스럽게 먼저 계산된다. DP 테이블(메모이제이션) 덕분에 각 건물의 건설 시간은 단 한 번만 계산되므로, 모든 노드와 간선을 한 번씩만 방문하는 것과 같아져 효율적으로 문제를 해결할 수 있다.

마무리 🤔

  • DP on DAG: 이 문제는 의존성을 가지는 작업들의 최소 완료 시간을 구하는 전형적인 ‘DAG 상에서의 DP’ 문제다.
  • Top-Down vs Bottom-Up:
    • Top-Down (재귀+메모이제이션): 내가 사용한 방법. 목표에서 시작하여 필요한 하위 문제를 재귀적으로 해결한다. 코드가 직관적이다.
    • Bottom-Up (반복문+큐): 위상 정렬(Kahn’s Algorithm)을 먼저 수행하며 순서대로 DP 테이블을 채워나가는 방식. 진입 차수(in-degree)가 0인 노드부터 시작하여 큐를 이용해 해결할 수 있다.
  • 재귀 깊이: Python에서 재귀를 사용할 때는 sys.setrecursionlimit()으로 최대 재귀 깊이를 넉넉하게 설정해주는 것이 중요하다.

위상 정렬 개념을 DP와 결합하여 해결하는 좋은 경험이었다.

⁂