[백준] 1005. ACM Craft - Python

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

1005번: ACM Craft

---

• 풀이
  • 승리하기 위해 건설해야 할 건물(W)를 건설하기 위해 이전 건설 루트를 알아내고 싶었다.
    • 실패(건설시작점이 여러군데 일 수 있다..)
  • '순서가 정해져 있는 작업'을 차례로 수행해야 할 때 그 순서를 결정
    • 위상 정렬
  • 건물 W를 건설완료 하는데 드는 최소 시간 + 이전 건물 건설 다 하고 넘어와야함
    • DP (다이나믹 프로그래밍)

https://chaemi720.tistory.com/220

위상 정렬(Topology Sort) 알고리즘

• 코드

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

# 테스트 케이스
T = int(input())
for _ in range(T):  
    # 건물의 개수, 건물 간의 건설 순서 규칙의 총 개수
    N, K = map(int,input().split())
    # 각 건물당 건설에 걸리는 시간
    time = [0]+list(map(int,input().split()))
    
    # 건설 순서 (order[i]를 건설 후 건설할 건물 번호)
    order = [[] for _ in range(N+1)]
    # 진입횟수(indegree[i] : i 직전에 건설된 건물 수)
    indegre = [0]*(N+1)
    for _ in range(K):
        X,Y = map(int,input().split())
        order[X].append(Y)
        indegre[Y] += 1
        
    # 승리하기 위해 건설해야 할 건물의 번호
    W = int(input())
    
    que = deque()
    # 진입 횟수가 0인 건물부터 시작
    for i in range(1,N+1):
        if indegre[i] == 0:
            que.append(i)
    
    # 걸리는 시간 dp
    result = time[:]
    while que:
        # 현 건물
        c = que.popleft()
        # c건물을 건설하고 건설 할 건물들 체크
        for i in order[c]:
            indegre[i] -= 1
            # 이 건물을 건설하기 건물들 중 최대시간을 더해야 함
            result[i] = max(result[i],result[c]+time[i])
            if indegre[i] == 0:
                que.append(i)
                # 원하는 건물?
                if i == W:
                    break
    print(result[W])