소스 코드

import sys
from collections import deque
input = sys.stdin.readline

# DP[i] = max(DP[선행 노드]들) + costs[i]

for _ in range(int(input().rstrip())):
    N, K = map(int, input().strip().split())
    costs = [0] + [*map(int, input().strip().split())]
    edges = [[] for _ in range(N + 1)]

    in_degree = [0] * (N + 1)

    # edge 및 진입 차수 기록
    for _ in range(K):
        pre, post = map(int, input().strip().split())
        edges[pre].append(post)
        in_degree[post] += 1

    DP = [0] * (N + 1)
    dq = deque()
    
    # 진입 차수 0인 노드들 덱에 넣기
    for v in range(1, N + 1):
        if in_degree[v] == 0:
            dq.append(v)
            DP[v] = costs[v]
    
    W = int(input().strip())

    # DP 메모이제이션을 채워주기 위해, 위상 정렬 순서에 기반하여 탐색 및 갱신 수행
    while dq:
        pre_v = dq.popleft()

        for post_v in edges[pre_v]:
            DP[post_v] = max(DP[post_v], DP[pre_v] + costs[post_v])
            in_degree[post_v] -= 1

            if in_degree[post_v] == 0:
                dq.append(post_v) 
    
    print(DP[W])

풀이 요약

1. 문제를 부분 문제로 나눠보면, 특정 건물을 짓기 위해 필요한 최소한의 비용은, 직전 선행 건물들까지의 최소 건설 비용들 중 가장 큰 비용(그래야 직전 선행 건물들을 그 비용에 다 지을 수 있으니)에다 본인 건물의 건설 비용을 더한 값이다.

   해당 논리에 따라 점화식은 다음과 같다.

   DP[i] = max(DP[선행 노드]들) + costs[i]

2. 위 점화식에 의해 DP 메모이제이션 배열을 채우기 위해, 진입 차수가 0인 노드들부터 탐색해나가면서 DP를 갱신해나가면 된다. 이 때 탐색 순서는 문제에서 주어진 조건인 특정 건물은 선행 건물들이 모두 건설되고 나서 건설 가능하다를 충족하기 위해 위상 정렬을 활용한다.

어려웠던 점, 배운 점

• DP 점화식까지는 잘 생각했고, 이제 탐색을 하면서 DP 리스트를 채워나가야하는데, 처음에는 단순 BFS로 돌렸다가 틀리게 나와서 다시 고민해봤고, 직접 테스트 케이스를 그림판에 그리면서 살펴보니까 위상 정렬 순으로 탐색하면 되겠다는 건 알아냈다.

  그런데 위상 정렬을 배운지가 너무 오래돼서.. BFS를 돌 때 후행 노드들을 위상 정렬 순으로 돌게끔하는 이상한 풀이(?)를 하는 기행을 벌였다..

  다른 사람 풀이를 보고 그제야 위상 정렬 활용법이 정확하게 생각나서 수정 후 제출해서 맞았다.

  빨리 진도 빼서 계획한 범위 내 알고리즘 유형들을 빨리 복습해야겠다..

  그리고 또 든 생각이, 역시 그래프 문제는 테스트케이스를 직접 그래프로 그려보면서 짚어가는데 이해가 빠르다는 생각이 들었다.