알고리즘 스터디 - 백준 1005번 : ACM Craft
문제 해석
특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간
- 건물을 짓는 순서가 존재하고 건설 조건이 존재함
- 1번을 짓고 2, 3번을 다 지어야 4번을 지을 수 있다.
- 단, 동시에 지을 수 있다.
입력
- T : 테스트케이스의 개수
- N, K : 건물의 개수, 건설 순서 규칙의 총 개수
- D1, ..., DN : 각 건물당 건설에 걸리는 시간
- X, Y : 규칙 건설 순서로 X를 짓고 난 다음에 Y를 짓는 것이 가능함
- W : 백준이가 승리하기 위해 건설해야 할 건물의 번호
어떤 알고리즘을 써야할까?
먼저 문제의 특징을 살펴보자
- 방향이 있는 그래프
- 선행 순서가 있어야 함
위상 정렬 알고리즘을 써서 노드의 진입 차수를 구하고 노드 순서를 구해야 함
알고리즘 코드
- 고민하고 고민하다 아이디어가 생각이 안나서 알고리즘 종류를 보니까 동적계획법이 있길래 위상정렬 알고리즘에다가 동적 계획법을 응용하여 문제를 풀었다.
import sys
from collections import deque
input = sys.stdin.readline
# 위상 정렬 알고리즘, degree : 진입 차수, graph : 그래프, dp : 걸리는 시간, node_time : 노드별 걸리는 시간, n : 노드 개수
def topology_sort(Degree, Graph, Dp, Node_time, n):
result = []
queue = deque()
for i in range(1, n+1):
if Degree[i] == 0:
queue.append(i)
Dp[i] = Node_time[i]
while queue:
current = queue.popleft()
result.append(current)
for i in Graph[current]:
Degree[i] -= 1
Dp[i] = max(Dp[current] + Node_time[i], Dp[i])
if Degree[i] == 0:
queue.append(i)
# 위상 정렬 배열 순서
return Dp
# 테스트 케이스
T = int(input())
# 정답 저장
answer = [0 for _ in range(T)]
for _ in range(T):
N, K = map(int, input().split())
# 각 노드별 걸리는 시간 1부터 시작이므로 [0]을 더해줌
node_time = [0] + list(map(int, input().split()))
degree = [0] * (N+1)
graph = [[] for _ in range(N+1)]
dp = [0 for _ in range(N+1)]
for _ in range(K):
X, Y = map(int, input().split())
graph[X].append(Y)
degree[Y] += 1
W = int(input())
total_time = topology_sort(degree, graph, dp, node_time, N)
print(total_time[W])
Author And Source
이 문제에 관하여(알고리즘 스터디 - 백준 1005번 : ACM Craft), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@guri_coding/알고리즘-스터디-백준-1005번-ACM-Craft저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)