[백준/파이썬] 1005번 ACM Craft 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1005번 ACM Craft
• 문제풀이 코드 GitHub 링크
• 제출 언어: PyPy 3
• 선정 이유: (2026-03-10 기준) solved.ac에서 푼 사람 수 19,920명, 평균 시도 3.18회로 입문~중급 구간에서 막히기 쉬운 대표 문제

풀이

문제

건물마다 건설 시간이 있고, 선행 건물 규칙(X를 지은 뒤 Y 가능)이 주어질 때 목표 건물 W를 가장 빨리 완성하는 시간을 구하는 문제입니다.

핵심은 단순히 선행 건물 개수를 세는 게 아니라,
W까지 오는 여러 경로 중 가장 오래 걸리는 경로 시간을 정확히 계산해야 한다는 점입니다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

import sys
from collections import deque

read = sys.stdin.readline

t = int(read())
answers = []

for _ in range(t):
    n, k = map(int, read().split())
    build_time = [0] + list(map(int, read().split()))

    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    for _ in range(k):
        x, y = map(int, read().split())
        graph[x].append(y)
        indegree[y] += 1

    target = int(read())

    # dp[i]: i번 건물을 "완성"할 수 있는 가장 빠른 시간
    dp = [0] * (n + 1)
    q = deque()

    # 선행 건물이 없는 건물부터 시작
    for i in range(1, n + 1):
        if indegree[i] == 0:
            dp[i] = build_time[i]
            q.append(i)

    # 위상 정렬 + 최장 경로 DP
    while q:
        cur = q.popleft()

        for nxt in graph[cur]:
            if dp[nxt] < dp[cur] + build_time[nxt]:
                dp[nxt] = dp[cur] + build_time[nxt]

            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    answers.append(str(dp[target]))

print("\n".join(answers))

설명

이 문제는 DAG(사이클 없는 방향 그래프) 위상 정렬 + DP 조합으로 풉니다.

• 선행 규칙 X -> Y는 간선으로 보면 방향 그래프입니다.
• Y를 짓기 전에 X가 끝나야 하므로 indegree(진입차수) 기반 위상 정렬이 가능합니다.
• dp[Y] = max(dp[Y], dp[X] + build_time[Y]) 로 갱신하면, Y에 도달하는 모든 경로 중 최댓값(가장 오래 걸리는 선행 체인)을 유지할 수 있습니다.

시간 복잡도는 테스트케이스당 O(N + K) 입니다.

즉, 이 문제의 포인트는 “선행 건물 수”가 아니라 “선행 경로 중 최대 누적 시간”을 구하는 것입니다.

---

• 백준 문제풀이 전체 목록 보기

---