[BOJ] 1005번 : ACM Craft(위상 정렬, dp)

접근

순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제.

느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 같다. 또한 사이클이 존재하지 않는다면, 위상정렬을 통해 또한 해결이 가능할 것 같아 보였다.

결론적으로는 위상정렬을 사용해서 해결했다.

 

위상정렬은 뭔가?

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

"유향 그래프의 꼭짓점들의 변의 방향을 거스르지 않도록 나열하는 것" 위키백과의 정의이다.

예시도 잘 들어져있는데, "대학의 선수과목"구조를 예로 들 수 있다. 위상정렬은 그래프의 사이클이 존재하면 안된다.

해결

위상정렬을 통한 해결과정을 생각해보자. 위상정렬의 시작점은 자신에게 진입하는 차수가 0인 정점들이다.

일반적으로는 이 정점을 출력하지만, 우리는 DP를 이용해서, 해당 정점과 연결되는 정점들까지의 최대 거리를 비교해서 업데이트 해준다. 원래라면 업데이트한 간선은 삭제한다. 근데 우리는 그렇게까지 안하고, 그냥 탐색한 정점의 진입차수를 1만큼씩 줄여준다. 

다시 진입 차수가 0인 정점을 찾아서, 다시 위의 과정을 반복한다. 반복과정엔 진입차수가 0인 정점들의 탐색을 위한 수단으로 Queue구조를 사용한다.

 

나는 매번 진입 차수가 0인 정점을 찾는건 비효율적이라고 생각해서, 만약 간선을 통해 탐색을 진행하고 차수를 줄였을 때 0이었다면, Queue에 추가하는 식으로 탐색을 이어나갔다.

추가적인 실수로 DP 테이블이 업데이트 됐을 때만 진입차수를 감소시켰는데, 그러면 안되고 무조건 감소를 시켜줘야한다. 그래야지 위상정렬의 의미와 맞다.

 

코드

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    build_times = list(map(int, input().split()))
    
    graphs = defaultdict(list)
    build_orders = defaultdict(int)
    for _ in range(K):
        a, b = map(int, input().split())
        build_orders[b] += 1
        graphs[a].append((b, build_times[a-1]))
    winning_building = int(input())
    
    que = deque([])
    dp = [0] * (N+1)
    
    for i in range(1, N+1):
        if not build_orders[i]:
            que.append(i)

    while que:
        v = que.popleft()
        

        for nv, nw in graphs[v]:
            if dp[nv] < dp[v] + nw:
                dp[nv] = dp[v] + nw
            build_orders[nv] -= 1
            if build_orders[nv] == 0:
                que.append(nv)
                    
    print(dp[winning_building] + build_times[winning_building-1])