[백준 1005번] ACM Craft (Python3)

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

T = int(input())
for test in range(T):
  N,K = map(int,input().split())
  time = list(map(int,input().split()))

  child = [[] for i in range(N+1)]
  indegree = [0]*(N+1)
  pretime = [0]*(N+1)

  for i in range(K):
    x1,x2 = map(int,input().split())
    child[x1].append(x2)
    indegree[x2] += 1

  W = int(input())

  dq = deque()
  for i in range(1,N+1):
    if indegree[i] == 0:
      dq.append(i)

  finish = False
  while dq:
    if finish:
      break
    x = dq.popleft()
    for i in child[x]:
      indegree[i] -= 1
      pretime[i] = max(pretime[i],pretime[x]+time[x-1])
      if indegree[i] == 0:
        dq.append(i)
        if i == W:
          finish = True
          break
          
  print(pretime[W]+time[W-1])

 

위상정렬을 알기 전에 위상정렬로 풀어야되는지 모르고, BFS로 풀었다가, 다 익스트라 변형해서 풀었다가, 여러가지 방법을 며칠에 걸쳐서 시도해도 못풀었었던 문제이다.

 

위상정렬로 푸니까 바로 깔끔하게 정답이 나왔다.

 

기본적인 알고리즘은 위상정렬과 동일하고, 이때 추가로 pretime이라는 리스트를 만들어줘서 건물을 짓기 전에 걸린 시간들 중 최댓값을 저장하도록 하였다. 즉, 4번 건물을 짓기 위해서 2번, 3번 건물을 지어야 한다면, pretime[4]는 2번건물을 짓는데 걸린시간과 3번 건물을 짓는데 걸린시간 중 더 큰 값인 셈이다.

 

그리고 마지막에는 최종 건물을 짓는데 걸리는 시간을 더해서 출력한다.

 

 

오늘의 교훈) 뻘짓하지말자