백준 1005번 파이썬

문제

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

1005번: ACM Craft

풀이

처음 시도한 풀이(시간 초과)

처음에는 단순히 목표 노드에서 연결된 노드를 거꾸로 접근해 가면 dp배열을 업데이트 시켰다.

def d(i: int):
    if not graph[i]:
        dp[i] = times[i]
        return dp[i]
    dp[i] = max(map(d, graph[i])) + times[i]
    return dp[i]


for _ in range(int(input())):
    N, K = map(int, input().split())
    times = [0] + list(map(int, input().split()))
    graph = [[] for __ in range(N+1)]
    dp = [0] * (N+1)
    for ___ in range(K):
        X, Y = map(int, input().split())
        graph[Y].append(X)
    W = int(input())
    
    print(d(W))

맞은 풀이

시간 초과 판정을 받고 탑다운 방식이 아닌 바텀업 방식으로 생각해보았다.

 

진입차수가 0인 노드부터 하나씩 건물 건설에 걸리는 시간을 확정 지어 위상 정렬로 풀 수 있다고 판단했다.

import sys
from collections import deque

input = sys.stdin.readline

for _ in range(int(input())):
    N, K = map(int, input().split())
    times = [0] + list(map(int, input().split()))
    graph = [[] for __ in range(N + 1)]
    in_degree = [-1] + [0] * N  # 진입 차수 초기화
    dp = [0] * (N + 1)  # dp 테이블 초기화

    for ___ in range(K):
        X, Y = map(int, input().split())
        graph[X].append(Y)
        in_degree[Y] += 1
    W = int(input())

    q = deque()
    for idx, val in enumerate(in_degree):
        if val == 0:  # 진입 차수가 0이면 큐에 삽입
            dp[idx] = times[idx]  # 건물 건설에 걸리는 시간 확정
            q.append(idx)
    while q:
        prev = q.popleft()
        for next in graph[prev]:  # 연결된 노드 탐색
            dp[next] = max(dp[next], dp[prev] + times[next])  # 건물 건설에 걸리는 시간 업데이트
            in_degree[next] -= 1  # 진입 차수 -1
            if in_degree[next] == 0:  # 새롭게 진입 차수가 0이된 노드 큐에 삽입
                q.append(next)
    print(dp[W])