1005 ACM Craft (Python)

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

 

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로 들어가버리면 이전에 짓고 있던 건물들과 섞여버림

 

위상 정렬이 체화되지 않아 까먹었던 상태라

bfs로 어떻게든 맞았습니다 띄웠지만

 

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 역탐색 재귀로 풀면 복잡하게 수식 죽 쓸 필요도 없다.