[python] 백준 1005: ACM Craft

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

 

위상정렬, 그리고 dp를 이용하여 푸는 문제이다. 위상정렬 개념에 대해 잘 몰라서 학습해보았다.

"위상 정렬(Topological Sort)은 방향 그래프의 모든 노드를 방향성을 지키며 순서대로 나열하는 알고리즘" 으로 정리할 수 있을 것 같다. 관련 개념에 대해 조금 더 공부해보면 좋을 것 같다. 

#백준 1005 : ACM Craft

#필요 라이브러리 import

import sys

from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):

n,k = map(int,input().split())

time = [0] + list(map(int,input().split()))

rule = [[] for _ in range(n+1)]

degree = [0 for _ in range(n+1)]

dp = [0 for _ in range(n+1)]

for _ in range(k):

a,b = map(int,input().split())

rule[a].append(b)

degree[b] += 1

q = deque()

for i in range(1,n+1):

if degree[i] == 0:

q.append(i) 

dp[i] = time[i] 

while q:

a = q.popleft()

for i in rule[a]:

degree[i] -= 1

dp[i] = max(dp[a]+time[i],dp[i])

if degree[i] == 0:

q.append(i)

 

res = int(input())

print(dp[res])

 

 

* 핵심 아이디어: 진입 차수가 0인 건물부터 큐에 추가하여 위상정렬을 시작하고, 큐에서 하나씩 꺼내면서 해당 건물이 영향을 미치는 다음 건물을 처리하는 것!