[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다.

그럼 문제를 보자

문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다.
보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다.

그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다.

[python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 )

 

만약 이렇게 그래프가 존재한다. 그럼 각 노드에 in degree를 구하면 아래와 같다.

node	1	2	3	4	5	6	7	8
in degree	0	1	1	1	1	1	2	1

 

그럼 아무 의존성 없이 만들 수 있는 건물은 1번이다. 따라서 1번을 q에 삽입하고 BFS를 진행한다.

node	1	2	3	4	5	6	7	8
in degree	0	0	0	1	1	1	2	1

이제 1노드를 뽑아서 인접한 노드인 2와 3에 1의 소요비용을 더해준다. 즉, 2번까지 구하기 위해서는 30초가 걸린다는 소리다. 그리고 3을 만들기 위해서는 11초가 걸린다는 의미다. 그리고 2와 3의 in degree접선을 제거해준다. 그럼 2와 3의 in degree는 0이 되고 0이 되었기 때문에 q에 넣어준다.

 

node	1	2	3	4	5	6	7	8
in degree	0	0	0	0	0	0	2	1

이제 큐에 존재하는 2와 3을 뽑고 인접하는 4,5,6노드에 자신의 자기까지 걸리는 시간을 더해준다. 그리고 접선을 제거하고 0인 경우 큐에 넣어준다. 그럼 큐에는 4,5,6이 들어간다.

 

이제 큐에서 4,5,6을 뽑고 인접한 노드에 값을 더해준다. 그런데 7의 경우에는 5와 6이 접하고 있다. 즉, 7을 만들기 위해서는 5와 6이 만들어져야 한다. 따라서 둘 중에 소요 시간이 큰 값을 7에 더해 주어야 한다. 이후에는 큐에 목표값인 7이 들어왔기 때문에 더 이상 BFS를 실행하지 않고 탈출해준다. 그럼 결과적으로 39라는 소요 시간이 걸린다.

이제 원리는 확인했으니 코딩을 진행해주면 된다.

위상정렬과 dp를 합쳐주면 위의 코드를 구현할 수 있다.

"""
DAG 위상정렬을 사용하는거 같은 느낌 어렵다.
1. adj와 위상정렬용 memo 구하기
2. BFS로 위상정렬 시작한다.
3. 추가적으로 dp를 돌리면서 점화식을 돌린다.
4. 목표 노드에 도착하면 루프 종료시킨다.
5. 해당 값을 반환한다.
"""
import sys
input = sys.stdin.readline

def staller():
    N,K = map(int, input().split())
    cost = [0] + list(map(int, input().split())) # cost설정
    adj = [[] for i in range(N+1)]
    memo = [ 0 for i in range(N+1)]
    for _ in range(K):
        a,b = map(int, input().split())
        adj[a].append(b)
        memo[b] += 1
    W = int(input())

    from collections import deque
    q = deque([])
    for i in range(1, N+1): # 시작할 노드들을 찾는다.
        if memo[i] == 0:
            q.append(i)
    # BFS로 위상정렬 시작하기
    dp = [-1 for i in range(N+1)]
    for i in q:
        dp[i] = cost[i]

    while q:
        for _ in range(len(q)):
            node = q.popleft()
            if node == W:
                q = []
                break
            childs = adj[node]
            for child in childs:
                if dp[child] == -1:# 갱신이 된적 없음
                    dp[child] = dp[node] + cost[child]
                else:
                    if dp[child] < dp[node] + cost[child]:
                        dp[child] = dp[node] + cost[child]
                memo[child] -= 1
                if memo[child] == 0:
                    q.append(child)
    print(dp[W])
T = int(input())
for _ in range(T):
    staller()