글 읽기 - 위상정렬 DP 썼을 때와 안썼을 때 차이

meanaccto 2년 전 1

위상정렬을 이용해 문제를 풀었고, DP를 썼을 때와 안썼을 때 각각 풀어봤는데, DP를 사용해야만 통과를 하더라구요.

굳이 DP 사용하지 않고 하나의 계층에 있는 원소를 모두 돌아준 후 해당 계층의 max값을 더하면 된다고 생각해서 로직은 같아 보이는데 정확히 어떤 차이 때문에 오답이 뜨는지 모르겠습니다.

어느 부분이 잘못된건지 짚어주시면 정말 감사하겠습니다.

# DP 사용하지 않았을 때 (오답)
import sys
from collections import deque
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    ans = 0
    n, k = map(int, input().split())
    time_per_build = list(map(int, input().split()))
    in_degree = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(k):
        a, b = map(int, input().split())

        in_degree[b] += 1
        graph[a].append(b)
    
    w = int(input())
    fin = False
    queue = deque()

    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append(i)

    while queue:
        max_value = -1
        for i in range(len(queue)):
            current = queue.popleft()
            if current == w:
                max_value = time_per_build[current - 1]
                fin = True
                break
            
            max_value = max(max_value, time_per_build[current-1])

            for g in graph[current]:
                in_degree[g] -= 1

                if in_degree[g] == 0:
                    queue.append(g)


        ans += max_value
        if fin:
            break

    print(ans)

# DP 썼을 때 (정답)
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    time_per_build = list(map(int, input().split()))
    in_degree = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
     
    for _ in range(k):
        a, b = map(int, input().split())
        in_degree[b] += 1
        graph[a].append(b)

    w = int(input())
    
    dp = [0] * (n + 1)
    queue = deque()

    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append(i)
            dp[i] += time_per_build[i-1]

    while queue:
        current = queue.popleft()

        for g in graph[current]:
            in_degree[g] -= 1
            dp[g] = max(dp[g], dp[current] + time_per_build[g-1])

            if in_degree[g] == 0:
                queue.append(g)

    print(dp[w])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

위상정렬 DP 썼을 때와 안썼을 때 차이

meanaccto 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말