1 minute read

문제

접근 방법

작업 순서가 정해져 있는 문제이기 때문에 Topological sort으로 문제를 접근했다.

동시에 처리되어야 하는 것들에 유의하면서 정해진 작업 순서대로 처리하면 풀릴 거라고 생각했다.

A 다음 작업이 B라고 할 때, B의 indegree를 감소시키고 B의 건설 시간을 update 해놓는다. udpate 해놓는 이유는 A->B, C->B일 경우, A까지 짓는데 걸린 작업시간 + B의 작업시간과 C까지 짓는데 걸리는 작업시간 + B의 작업시간을 비교하여 더 큰 것을 저장해야 하기 때문이다.

이전까지 한 작업 시간을 기록하기 위해서 메모이제이션을 활용하면 시간을 줄일 수 있다. building[i]는 건물 i까지 건설하는데 걸리는 최소 시간을 기록한다.

이 문제는 금방 풀 문제였는데.. 문제를 잘못 이해했었다… 1->2와 1->3이 있을 때 2의 소요시간은 10, 3의 소요시간은 100이라면 2의 소요시간도 100이 되는걸로 이해했다….

문제 똑바로 읽자.

정답 코드

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

"""
작업 순서라는 문제가 topological sort를 떠올리게 했다.
topological sort
"""

T = int(input())
answers = []
for _ in range(T):
  n, k = map(int, input().split())
  times = [0] + list(map(int,input().split()))
  indegree = [0] * (n+1)
  graph = [[] for _ in range(n+1)]
  for _ in range(k):
    x,y = map(int, input().split())
    indegree[y] += 1
    graph[x].append(y)
  goal = int(input())

  q = deque()
  building = [-1]*(n+1)
  for i in range(1,n+1):
    if indegree[i] == 0:
      q.append(i)
      building[i] = times[i]
  
  while q:
    node = q.popleft()
    for adj in graph[node]:
      indegree[adj]-=1
      building[adj] = max(building[adj], building[node] + times[adj])
      if indegree[adj] == 0:
        q.append(adj)

  answers.append(building[goal])
for ans in answers:
  print(ans)

```

You May Also Enjoy