[Python] 백준 1005번 : ACM Craft

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

1005번: ACM Craft

---

💡 문제 풀이

동적 프로그래밍과 위상정렬을 합친 문제이다.

위상정렬을 통해서 해당 노드까지 가는 길을 파악하고 DP로 최적화한다.

이해를 위해서 문제에서 제공된 첫 예제로 이해해 보자.

 

1부터 4까지 가기 위해서는 1 → 2, 3 → 4로 가야 한다.

DP[i]에서 저장되는 값은 정점 i까지 도달했을 때의 최댓값이다.

4로 가는 길은 2가지이지만, 각 경로에 대한 비용을 따져서 최댓값으로만 최신화시켜주면 된다.

✔️ 느낀 점

DP 문제를 정말 어려워하는데 이번에도 느낀 점이 존재한다.

바로 DP라는 개념이 들어오게 된다면 그 자료구조에 어떤 값을 저장할지 고민하기이다.

처음에는 역으로 올라가는 방법으로 생각했다. 4에 대한 값을 찾는다면 4부터 끝까지 내려가고,

끝까지 내려가기 위해서 DFS를 사용했지만 같은 층에 대해서 두 번의 연산을 해서 문제가 발생했었다.

💻 코드

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

def solution(w, graph, inDegree, d):
    size = len(graph)
    DP = [0] * size
    q = deque()
    
    for i in range(1, size):
        if inDegree[i] == 0:
            q.append(i)
            DP[i] = d[i]
    
    while q:
        v = q.popleft()
        
        for n in graph[v]:
            inDegree[n] -= 1
            DP[n] = max(DP[n], DP[v] + d[n])
            if inDegree[n] == 0:
                q.append(n)
    
    return DP[w]

T = int(input())

for _ in range(T):
    n, k = map(int, input().split())
    d = [0] + list(map(int, input().split()))
    graph = [[] for _ in range(n+1)]
    inDegree = [0] * (n+1)
    
    for _ in range(k):
        a, b = map(int, input().split())
        graph[a].append(b)
        inDegree[b] += 1
    
    w = int(input())
    print(solution(w, graph, inDegree, d))