백준 1005 ACM Craft 문제풀이

문제 

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

1005번: ACM Craft

 

 

문제 접근 방식

두 노드간 관계가 주어지기 때문에 위상정렬을 사용하려 했다. 또한, 특정 노드를 가장 빨리 짓기 위해서는 이전에 선행되었던 노드들의 건설이 동시에 이뤄져야한다.(예시에서 2,3번이 동시에 건설되어야함. 2 > 3 이런식으로 순차적으로 건설 X). 선행 노드(2,3번)의 건설이 모두 완료되어야 다음 노드(4번)를 진행할 수 있기 때문에 선행 노드까지의 건설 시간을 비교해야 했고, 이 건설 시간을 저장할 자료구조가 필요했다.

 

아래와 같이 특정 노드까지 걸리는 시간을 저장하는 자료구조를 만들었고, 이를 활용해서 점화식을 세울 수 있었다(DP)

1. 점화식 정의
total_costs[i] = i 노드까지 걸리는 최소 시간

2. 점화식
total_costs[i] = max(total_costs[j]+cost[i]) //j = i의 선행 노드들, costs[i] = i 노드 건설 시간

 

 

위상정렬을 통해 노드들을 순회하고, 이웃한 노드들의 진입차수를 -1 할 때 total_costs[i]( i 까지의 최소 시간) 도 같이 갱신해준다. 이렇게 하면 위상정렬을 완료할 때, 각 노드까지의 최소시간이 total_costs 에 저장된다.

 

 

시간 복잡도

위상정렬을 하기 때문에 O(V+E) 가 걸리며, 점화식을 갱신하는데 걸리는 시간은 따로 발생하지 않는다. 그러므로 전체 시간복잡도는 O(V+E)이고, V=1e3 , E=1e5 이기 때문에 시간내에 동작한다.

 

코드

import sys
input=sys.stdin.readline
print=sys.stdout.write

if __name__=='__main__':

    
    t=int(input())
    for _ in range(t):
    
    	##### 입력처리 #####
        n, k = map(int, input().split())

        adj = [[] for _ in range(n + 1)]
        costs = list(map(int, input().split()))
        costs.insert(0, 0)

        ## total_costs[i] = i 노드까지 오는데 걸리는 최소비용
        total_costs = [0] * (n + 1)
        in_degree = [0] * (n + 1)

        # 그래프 및 진입차수 초기화
        for _ in range(k):
            a, b = map(int, input().split())
            adj[a].append(b)
            in_degree[b] += 1

        end_point = int(input())

        ##### 입력처리 완료 #####

        ##### 큐에 진입차수가 0 인 노드를 넣어주고, 해당 노드의 total_costs[i] 를 자신의 cost로 갱신한다.
        q = []
        for i in range(1, n + 1):
            if in_degree[i] == 0:
                q.append(i)
                total_costs[i] = costs[i]

        while q:
            now = q.pop(0)
            for next in adj[now]:
                # [now 까지의 최소비용] + [next 비용] 을 구하고, 이전에 구한 값과 비교하여 큰 값으로 갱신한다
                total_costs[next] = max(total_costs[next], total_costs[now] + costs[next])
                in_degree[next] -= 1

                if in_degree[next] == 0:
                    q.append(next)

        print(str(total_costs[end_point])+'\n')

 

 

회고

위상 정렬을 사용하여 그래프를 탐색할 때 어떻게 DP를 활용할 수 있는지 경험할 수 있었다.