백준 1005번 ACM Craft
설명
진입 차수 배열을 만들어서 해당 건물 전에 미리 지어야 할 건물이 있으면 해당 건물을 인덱스로해서 배열의 값을 1씩 증가시킨다.
각 건물마다 지을 때까지 걸리는 시간을 넣기위한 배열 dp를 만든다.
맨 처음에 진입 차수가 0인 건물을 큐에 다 집어 넣고, 그러면서 동시에 해당 건물의 dp 값도 해당 건물을 짓는데 걸리는 시간으로 다 바꿔준다(진입 차수가 0이니깐 그냥 그 해당 건물을 바로 지을 수 있음).
큐를 왼쪽부터 하나씩 빼면서 그 건물 다음으로 지을 수 있는 건물을 확인하면서 진입 차수를 1씩 빼준다.
(다음 지을 수 있는 건물의 dp 값)과 (바로 전건물의 dp + 다음 지을 수 있는 건물 건설시간) 이 둘을 비교해서 더 큰 값으로 계속 업데이트해나간다.
진입 차수를 1씩 빼면서 진입 차수가 0이 되면 큐에 넣는다.
최종적으로 큐가 비면 나온다음 도착 건물의 dp 값이 정답
코드
import sys
import collections
from typing import List
input = sys.stdin.readline
class Solution:
def ACM_craft(self, N: int, K: int, time: List[int],
graph: List[List[int]], degree: List[int], W: int):
dp = [0]*(N+1) # 각 건물마다 완료 시간 넣는 dp
q = collections.deque()
for i in range(1, N+1):
# 진입 차수가 0이면 데크에 다 넣고, dp에 해당 건물 건설 시간 넣음
if degree[i] == 0:
q.append(i)
dp[i] += time[i]
"""큐에서 하나씩 빼면서 그래프 돔
그 때마다 차수를 하나씩 빼주고
dp는 pop_node dp 값이랑
그래프 돌면서 나오는 정점의 건물 건설 시간이랑 더한다음
기존 dp랑 비교해서 max 값 삽입"""
while q:
pop_node = q.popleft()
for i in graph[pop_node]:
degree[i] -= 1
dp[i] = max(dp[i], dp[pop_node] + time[i])
if degree[i] == 0:
q.append(i)
return dp[W]
for _ in range(int(input())):
# 건물의 개수, 건물간의 건설순서 규칙
N, K = map(int, input().split())
"""각 건물당 건설에 걸리는 시간 0은 아에 없어서
0으로 두고 인덱스 1부터 넣음."""
time = [0] + list(map(int, input().split()))
graph = collections.defaultdict(list)
degree = [0]*(N+1) # 진입 차수
for _ in range(K):
u, v = map(int, input().split())
graph[u].append(v)
degree[v] += 1 # v, 진입 차수 1 증가
W = int(input()) # 마지막 건설 건물 번호
print(Solution().ACM_craft(N, K, time, graph, degree, W))