알고리즘 스터디 - 백준 1005번 : ACM Craft

문제 해석

특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간

• 건물을 짓는 순서가 존재하고 건설 조건이 존재함
• 1번을 짓고 2, 3번을 다 지어야 4번을 지을 수 있다.
• 단, 동시에 지을 수 있다.

입력

1. T : 테스트케이스의 개수
2. N, K : 건물의 개수, 건설 순서 규칙의 총 개수
3. D1, ..., DN : 각 건물당 건설에 걸리는 시간
4. X, Y : 규칙 건설 순서로 X를 짓고 난 다음에 Y를 짓는 것이 가능함
5. W : 백준이가 승리하기 위해 건설해야 할 건물의 번호

어떤 알고리즘을 써야할까?

먼저 문제의 특징을 살펴보자

1. 방향이 있는 그래프
2. 선행 순서가 있어야 함

위상 정렬 알고리즘을 써서 노드의 진입 차수를 구하고 노드 순서를 구해야 함

알고리즘 코드

• 고민하고 고민하다 아이디어가 생각이 안나서 알고리즘 종류를 보니까 동적계획법이 있길래 위상정렬 알고리즘에다가 동적 계획법을 응용하여 문제를 풀었다.

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])