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

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

1005번: ACM Craft

간단한 위상정렬 문제이다.

내가 간단하다고 말하는 기준은 좀 어이없을 수 있지만, 내가 푼 풀이법 그러니까 내 코드가 구글링했을 때 수두룩하게 나오는 다른 사람의 코드와 거의 동일하면 간단한 문제라고 생각한다 ㅋㅋ

풀이법은 다음과 같다.

1. 위상 정렬의 첫 시작은 아무것도 건들지 않은 상태에서 진입차수가 0인 것부터 시작해주면 된다.

2. 하나씩 탐색하면서 해당 노드까지 가는 최장거리를 갱신한다. 이 때 해당 노드의 진입차수가 아직 남아있더라도 max 연산을 통해 모든 경우에서 최댓값을 구해준다.

3. 이 과정에서 진입차수가 0이 된다면 큐에 넣어서 다음 탐색을 위한 발판으로 한다.

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def topology_sort():
  ans = [0] * (n+1)
  dq = deque()
  
  # 진입차수가 0인것부터 시작
  for i in range(1,n+1):
    if indegree[i] == 0:
      dq.append(i)
      ans[i] = time[i]
  
  while dq:
    start = dq.popleft()

    for next in construction[start]:
      ans[next] = max(time[next] + ans[start],ans[next])
      indegree[next] -= 1
      if indegree[next] ==0:
        dq.append(next)
        
  return ans[w]

if __name__ == "__main__":
  t = int(input())
  for _ in range(t):
    n,k = map(int,input().split())
    
    construction = [[] for _ in range(n+1)]
    indegree = [0] * (n+1)
    
    time = [0] + list(map(int,input().split()))
    for _ in range(k):
      x, y = map(int,input().split())
      construction[x].append(y)
      indegree[y] += 1
    w = int(input())
    
    print(topology_sort())