[골드 3] 백준 1005 - ACM Craft (파이썬)

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

풀이

• 각 건물은 건설 완료에 특정 시간이 걸림.
• 어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수도 있음.
• 목표 건물 W를 짓기까지의 최소 시간을 구해야 함.

1. 진입 차수 계산 및 그래프 구성
   • count[y] += 1은 y번 건물을 짓기 전 지어야 할 건물 개수를 누적함.
   • adj[x].append(y)는 x 건물 후에 y 건물을 지을 수 있다는 의미.
2. 초기 시작 노드 설정 (진입 차수가 0인 노드)
   • 진입 차수가 0인 건물은 바로 지을 수 있으므로 queue에 삽입.
   • finish[i] = D[i]로 초기화.
3. 위상 정렬 + DP
   • u를 짓고 나면 그 다음 건물 v는 finish[v] = max(finish[v], finish[u] + D[v])로 업데이트함.
   • 즉, 선행 건물 중 가장 늦게 지어진 시간에 본인 건설 시간 더하기.
   • 선행 건물이 모두 끝났을 때(count[v] == 0) 큐에 삽입.
4. 정답 출력
   • print(finish[w])로 목표 건물의 건설 완료 시간 출력.

코드

# 백준 1005 - ACM Craft
# 분류 : 위상 정렬

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

T = int(input())

for _ in range(T) :
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    count = [0] * N

    for _ in range(K) :
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        adj[x].append(y)
        count[y] += 1
    
    w = int(input())
    w -= 1

    finish = [0] * N
    queue = deque()
    for i in range(N) :
        if count[i] == 0 :
            queue.append(i)
            finish[i] = D[i]
    
    while len(queue) != 0 :
        u = queue.popleft()

        for v in adj[u] :
            count[v] -= 1
            finish[v] = max(finish[v], finish[u] + D[v])
            if count[v] == 0 :
                queue.append(v)
    
    print(finish[w])

DP 사용 코드

# 백준 1005 - ACM Craft
# 분류 : 위상 정렬

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

T = int(input())

for _ in range(T) :
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    adj = [[] for _ in range(N)]

    for _ in range(K) :
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        adj[x].append(y)
    
    w = int(input())
    w -= 1

    cache = [-1] * N
    def dp(u) :
        if cache[u] != -1 :
            return cache[u]
        
        ret = D[u]
        for v in adj[u] :
            ret = max(ret, dp(v) + D[u])
        
        cache[u] = ret
        return ret

    print(dp(w))