[백준] 1005번 ACM Craft(python)

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

1005번: ACM Craft

 

1. 난이도 골드 3

 

2. 문제 해결 방법

 

건물을 짓는 순서가 정해져 있으며, 가장 빨리 지을 때까지의 최소시간을 알아내야한다.

 

따라서 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘인 위상정렬을 이용해 문제를 해결했다.

 

value라는 새로운 list를 만들고, value에는 그 건물을 짓기 위한 시간을 누적해 저장한다.

 

value 가 0인 경우는 아직 시간 측정이 안 된 건물이니 value[i] = value[now] + time[i] 하고,

 

value가 0이 아닌 경우는 기존 value 값과  value[now] + time[i]  중 더 큰 값을 넣는다.

 

=> 예시)

4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야 한다.

2번 건물을 짓고 4번 건물을 지으면 21초만에 지을 수 있지만 3번 건물을 짓지 못했으므로 건설할 수 없다.

즉, 4번 건물을 짓기 위해 지어놓아야 하는 건물들 중 제일 오래 걸리는 건물의 시간을 더해야한다.

따라서 3번 건물을 지을 때까지 걸린 시간과 2번 건물을 지을 때까지 걸린 시간의 최댓값을 넣은 것!

 

      if value[i] == 0:
        value[i] = value[now] + time[i]
      else:
        value[i] = max(value[i],time[i]+value[now])

 

3. 내가 작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

t = int(input().rstrip()) #테스트케이스 수 입력

for i in range(t): 

  n,k = map(int, input().rstrip().split()) #n건물개수 k건설조건
  build = [[] for _ in range(n+1)] #건설조건
  indegree = [0] * (n+1) #진입차수
  value = [0] * (n+1)
  time = [0] + list(map(int, input().rstrip().split())) #걸리는 시간

  for i in range(k):
    d1, d2 = map(int, input().rstrip().split())
    build[d1].append(d2)
    indegree[d2] +=1

  q = deque()

  for j in range(1,n+1):
    if indegree[j] == 0:
      value[j] = time[j]
      q.append(j)

  while q:

    now = q.popleft()

    for i in build[now]:
      if value[i] == 0:
        value[i] = value[now] + time[i]
      else:
        value[i] = max(value[i],time[i]+value[now])
        
      indegree[i] -= 1

      if indegree[i] == 0:
        q.append(i)
  
  
  print(value[int(input().rstrip())]) #건설해야 하는 건물 번호