[파이썬 / 백준 1005번] ACM CRAFT

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

728x90

이거 하다가 몇날며칠을 고민했는지 모른다..

머리로는 그림이 그려지는데, 구현을 하려니까 너무너무너무 어려워서 결국 도움을 받았다.

 

검색을 해 보니까 위상정렬 문제라고 하는데,

위상정렬이라는 것을 처음 들었다..

이러니 절대 풀 수가 없지

 

무엇인가 혼자 해 보려고 했는데 안되서 좌절감을 느끼고 있었는데

애초에 몰랐던 거니까.. 이제 알게되어서 다행이라고 생각했다.

언제쯤 능숙하게 이것 저것 모두 구현할 수 있는 능력을 가지게 될까.

 

정렬 문제는 여러가지로 공부 해 봐야겠다.

 

from sys import stdin
from collections import deque
input=stdin.readline
T=int(input())
for _ in range(T):
    N,K=map(int,input().split())
    dl=[0]+list(map(int,input().split())) #건물 올리는 시간
    bl=[[] for _ in range(N+1)]	#건물규칙
    inDegree=[0 for _ in range(N+1)] #진입차수
    dp=[0 for _ in range(N+1)]
    for i in range(K):	#건물 규칙 입력
        a,b=map(int,input().split())
        bl[a].append(b)
        inDegree[b]+=1
    q=deque()
    for i in range(1,N+1):
        if inDegree[i]==0:
            q.append(i)
            dp[i]=dl[i]
    
    while q:
        a=q.popleft()
        for i in bl[a]:
            inDegree[i]-=1
            dp[i]=max(dp[a]+dl[i],dp[i])
            if inDegree[i]==0:
                q.append(i)
    
    answer=int(input())
    print(dp[answer])