ACM Craft (1005번) - 백준 (BOJ)

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

1005번: ACM Craft

 

 

백준 - ACM Craft (1005번)

 

난이도 : Gold 3

알고리즘 : Topological Sorting (위상 정렬)

Time Complexity : O( N + K )

 

 

import sys
input = sys.stdin.readline


def testcase(N, K):
    cost = [0] + list(map(int, input().split()))
    dgr = [0] * (N+1)
    memo = [0] * (N+1)
    graph = [[] for _ in range(N+1)]
    for _ in range(K):
        p, c = map(int, input().split())
        graph[p].append(c)
        dgr[c] += 1
    W = int(input())
    q = [i for i in range(1, N+1) if not dgr[i]]
    while q:
        p = q.pop()
        if p == W:
            return str(cost[p])
        for c in graph[p]:
            memo[c] = max(memo[c], cost[p])
            dgr[c] -= 1
            if not dgr[c]:
                q.append(c)
                cost[c] += memo[c]


if __name__ == '__main__':
    print('\n'.join(testcase(*map(int, input().split())) for _ in range(int(input()))))

 

 

위상 정렬을 활용하는 문제이다.

 

특정 노드(node)의 부모 개수를 "차수(degree)"라고 하면,

차수가 0인 노드는 부모가 없는 노드이다.

 

초기에 차수가 0인 (부모가 없는) 노드들을 큐에 넣어서 초기화하고,

큐에서 노드를 하나씩 꺼내서,

꺼낸 노드의 자식 노드들을 하나씩 탐색한다.

 

이 때, 현재 부모 노드가 방문한 자식 노드의 차수를 1 빼준다.

왜냐하면 방문했기 때문이다.

그리고 자식 노드의 차수가 0이 된다면 (즉, 모든 부모가 해당 자식 노드에 이미 방문했다면),

해당 자식 노드를 큐에 넣어준다.

 

그리고 차수가 0인 자식 노드 입장에서는,

이미 모든 부모 노드가 방문한 상태이므로

부모 노드들 중에서 가장 긴 소요시간을 가진 부모노드의 값을 가져와서,

자기 자신의 소요시간을 더하면

그 값이 자식 노드 번호의 건물을 짓기 위한 최소 소요시간이 된다.

 

위의 과정들을 거쳐서,

W 노드가 큐에 들어가게 되면

그 시점에서 W 노드의 소요시간이, 건물 W를 짓기 위한 최소 소요시간이 된다.