문제 설명
•
건물별 건설 시간과 선행 건물 조건이 주어질 때, 특정 건물을 완성하는 데 걸리는 최소 시간을 구하는 문제
예제 입력/출력
•
입력1
2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7
Plain Text
복사
•
출력1
120
39
Plain Text
복사
더보기
제약 조건
•
•
•
•
는 정수
문제 풀이
접근1 다익스트라 알고리즘
•
접근2 위상 정렬 (DP + 큐 활용)
◦
4번 건물을 건설하기 위해서는 2번과 3번 건물 모두 완성된 후에만 가능하다.
◦
또한, 4번 건물을 짓기 위한 시간은 (1 → 2의 시간)과 (1 → 3의 시간) 중 더 오래 걸리는 쪽을 기준으로 계산해야 한다.
◦
예제
▪
먼저 1번 건물을 건설 (10초 소요)
▪
1번이 끝나면 2번과 3번을 동시에 건설 시작
•
2번 건물 완성: 1초 후 (총 11초)
•
3번 건물 완성: 100초 후 (총 110초)
▪
4번을 건설하려면 2번과 3번이 모두 끝난 후 가능
•
3번이 더 오래 걸리므로 110초가 기준이 됨
•
이후 4번 건설 시작 (10초 추가)
•
최종적으로 120초가 소요됨
◦
문제 핵심
1.
2.
선행 건물이 여러 개일 경우 시간 계산을 어떻게 할 것인가? → DP
•
특정 건물을 짓기 위해 필요한 선행 건물 중 가장 늦게 끝나는 건물을 기준으로 시간 갱신
•
dp[i] = max(dp[선행 건물] + 건설 시간[i], dp[i])
풀이 코드
import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
D = [0] + list(map(int, input().split()))
adj_list = [[] for _ in range(N + 1)]
degree = [0] * (N + 1)
for _ in range(K):
X, Y = map(int, input().split())
adj_list[X].append(Y)
degree[Y] += 1
W = int(input())
q = deque()
dp = [0] * (N + 1)
for i in range(1, N + 1):
if degree[i] == 0:
q.append(i)
dp[i] = D[i]
while q:
cur_node = q.popleft()
for adj_node in adj_list[cur_node]:
degree[adj_node] -= 1
dp[adj_node] = max(dp[cur_node] + D[adj_node], dp[adj_node])
if degree[adj_node] == 0:
q.append(adj_node)
if cur_node == W:
break
print(dp[W])
Python
복사
