⚔️ 백준

---

📌 1005 ACM Craft

while now_building:
    build = heapq.heappop(now_building)
    B_t, B = build[0], build[1]
    total_time += B_t
    if B == win:
        break
    Qsize = len(now_building)
    next_building(B,now_building,build_order,indegree)
    # 다른 건물들도 동시에 지을 수 있기 때문에 고려
    for i in range(Qsize):
        now_building[i][0] -= B_t
        if now_building[i][0]==0:
            next_building(build[1],now_building,build_order,indegree)

heappush로 들어가버리면 이전에 짓고 있던 건물들과 섞여버림

sub_Q 라는 유예용 큐 선언해서 해결

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

# 다 지었으면 다음 건물 indegree 지워주고 
# 다음 건물을 지을까말까 확인하는 과정
def next_building(B,build_order,indegree,sub_Q):
    for next in build_order[B]:
        indegree[next]-=1
        if indegree[next] == 0:
            sub_Q.append(next)

T=int(input())
for _ in range(T):
    # 각 경기에 대한 정보 받아오기
    total_time=0
    N,K=map(int,input().split()) # N: 건물개수, K: 건물순서규칙개수
    build_time=[0]+list(map(int,input().split()))
    build_order={i:[] for i in range(N+1)}
    indegree=[0 for _ in range(N+1)]
    for _ in range(K):
        X,Y=map(int,input().split())
        build_order[X].append(Y) # X를 지은 후에 Y를 지을 수 있음
        indegree[Y]+=1
    win=int(input())
    # indegree가 0이 되면 건설시킬 수 있음
    # indegree가 0이 된 놈들은 전부 큐에 넣는다
    # 하나씩 넣을 때마다 다음에 지날 시간과 비교하여 
    # 더 낮으면 지날 시간을 변경한다

    # 처음 지을 건물들 우선순위 큐에 넣기
    now_building=[]
    for i in range(1,N+1):
        if indegree[i]==0:
            heapq.heappush(now_building,[build_time[i],i])
    # 짓기 시작
    while now_building:
        sub_Q=deque()
        build = heapq.heappop(now_building)
        B_t, B = build[0], build[1]
        total_time += B_t
        if B == win:
            break
        Qsize = len(now_building)
        next_building(B,build_order,indegree,sub_Q)
        # 다른 건물들도 동시에 지을 수 있기 때문에 고려
        for i in range(Qsize):
            now_building[i][0] -= B_t
            if now_building[i][0]==0:
                next_building(build[1],build_order,indegree,sub_Q)
        # 순서가 섞이니까 유예를 둔 뒤에 추가하기
        for b in sub_Q:
            heapq.heappush(now_building,[build_time[b],b])
    print(total_time

좀 길긴 하지만 일단 풀었는데 50몇퍼에서 틀렸습니다 뜸

# 다른 건물들도 동시에 지을 수 있기 때문에 고려
    for i in range(Qsize):
        now_building[i][0] -= B_t
        if now_building[i][0]==0:
            next_building(now_building[i][1],build_order,indegree,sub_Q)

찬찬히 봤더니 now_building[i][1] 이 부분이 build[1]로 되어있었다. 아니 그럼 예제는 어떻게 맞은거고 50%까진 어떻게 올라간거지;

예제랑 50퍼까지는 해당 정점과 무조건 이어졌는데 50퍼 이상부터는 해당 정점과 연결 안돼있는 것들도 indegree가 0이 되는듯.

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

# 다 지었으면 다음 건물 indegree 지워주고 
# 다음 건물을 지을까말까 확인하는 과정
def next_building(B,build_order,indegree,sub_Q):
    for next in build_order[B]:
        indegree[next]-=1
        if indegree[next] == 0:
            sub_Q.append(next)

T=int(input())
for _ in range(T):
    # 각 경기에 대한 정보 받아오기
    total_time=0
    N,K=map(int,input().split()) # N: 건물개수, K: 건물순서규칙개수
    build_time=[0]+list(map(int,input().split()))
    build_order={i:[] for i in range(N+1)}
    indegree=[0 for _ in range(N+1)]
    for _ in range(K):
        X,Y=map(int,input().split())
        build_order[X].append(Y) # X를 지은 후에 Y를 지을 수 있음
        indegree[Y]+=1
    win=int(input())

    # 처음 지을 건물들 우선순위 큐에 넣기
    now_building=[]
    for i in range(1,N+1):
        if indegree[i]==0:
            heapq.heappush(now_building,[build_time[i],i])
    # 짓기 시작
    while now_building:
        sub_Q=deque()
        build = heapq.heappop(now_building)
        B_t, B = build[0], build[1]
        total_time += B_t
        if B == win:
            break
        if B_t == 0:
            continue
        Qsize = len(now_building)
        next_building(B,build_order,indegree,sub_Q)
        # 다른 건물들도 동시에 지을 수 있기 때문에 고려
        for i in range(Qsize):
            now_building[i][0] -= B_t
            if now_building[i][0]==0:
                next_building(now_building[i][1],build_order,indegree,sub_Q)
        # 순서가 섞이니까 유예를 둔 뒤에 추가하기
        for b in sub_Q:
            heapq.heappush(now_building,[build_time[b],b])
    print(total_time)
                
# now_building[i][0] 부분에 build 써버림
# win을 만들면 종료되게 하는거 깜빡함 - 결과가 말해주니까 알았지만
# heappush로 들어가버리면 이전에 짓고 있던 건물들과 섞여버림

일단 맞았습니다는 떴음

if B_t == 0:
    continue

이거 삭제하니까 또 틀렸습니다 떴음

import sys

sys.setrecursionlimit(1000000)

def ACMcraft(n):
    if not graph[n]:
        return time[n]
    
    if dp[n] == -1:
    
        for bef in graph[n]:
            dp[n] = max(dp[n], ACMcraft(bef) + time[n])
    
    return dp[n]

input = sys.stdin.readline

T = int(input())
for _ in range(T):#재귀dp돌릴거임
    N, K = map(int, input().split())
    time = [-1] + list(map(int, input().split()))
    dp = [-1] * (N+1)
    graph = [[] for _ in range(N+1)] #선행과정 가리킴

    for _ in range(K):
        x, y = map(int, input().split())
        graph[y].append(x)
    W = int(input())

    print(ACMcraft(W))

https://www.acmicpc.net/source/83904073

아니 dp로 풀면 복잡하게 수식 죽 쓸 필요도 없네;
심지어 빠름.

import sys
from collections import deque
input = sys.stdin.readline
test = int(input())
time = []
ans = [0]*(test)
for t in range(test):
    n,k = map(int,input().split())
    time = [0] + list(map(int, input().split()))
    result = [0] * (n+1)
    adjacent = [[] for _ in range(n+1)]
    indegree = [0] * (n+1)
    for i in range(k):
        a,b = map(int,input().split())
        adjacent[a].append(b)
        indegree[b] += 1
    x = int(input())

    #위상정렬 start
    queue = deque()
    for i in range(1,n+1):
        if indegree[i] == 0:
            queue.append(i)
            result[i] = time[i]
    while queue:
        node = queue.popleft()
        if node == x:
            break
        for c in adjacent[node]:
            result[c] = max(result[c],result[node] + time[c])
            if indegree[c] == 1:
                queue.append(c)
            indegree[c] -= 1
    ans[t] = result[x]
    #위상정렬 end

for t in range(test):
    print(ans[t])

https://www.acmicpc.net/source/83651286

max() 함수를 쓰는게 키포인트인 것 같음.

https://cobokjang.tistory.com/23
https://woojeenow.tistory.com/entry/%EB%B0%B1%EC%A4%80-1005-ACM-Craft-c
https://blog.itcode.dev/posts/2021/06/01/a1005

'자신에게 필요한 선행 건물 중 최대 시간을 가진 건물 + 자기 자신에 걸리는 시간'이 자신이 만들어지는 최소 시간이다.

위상 정렬할 때 굳이 indegree가 0이거나 특정 조건(여기선 시간)이 충족돼야만 정보를 기록하는게 아니라 죄다 기록해버리고 최댓값만 남기는 식으로 하면 간단해지는듯

그리고 그게 dp라고 할 수 있고

위에 있는 간단한 재귀 코드는

만들어야할 건물로부터 역탐색을 했다.
'자신에게 필요한 선행 건물 중 최대 시간을 가진 건물 + 자기 자신에 걸리는 시간'을 재귀로 역탐색해서 if not graph[n]일 때 (indegree가 0인 기초 건물들) 종료 조건 걸어놓고, 이전 건물들의 시간을 전부 구했다면 해당 건물을 건축하는데까지 걸린 시간을 반환하는 식으로 코드 짬.

짠 사람 대단하긴 한데 흡수 할 수는 있을지도
알고 체화시키면 별거아닐듯
체화시키는게 문제지

그리고 임계경로 답지 보면서 왜 틀렸는지 확인하려고 했는데
이 문제가 임계경로랑 똑같아서
안 보고 직접 똑같이 재귀로 풀어보면 될듯