동주의 세상

Clean and minimal personal blog

백준 1005 해설 파이썬

Posted at — Jun 8, 2021

solved.ac class 5의 essential 문제로, 위상 정렬에 대한 이해가 있다면 어렵지 않게 풀수 있다.

위상 정렬에 대해서는 따로 알고리즘 포스팅에 정리해놓겠다.

문제를 풀때 사고방식은 이랬다. 특정 건물 K를 짓기 시작하는 시점은 이전에 지어야 하는 건물들 중 가장 오래 걸리는 건물들을 선택해서 도달한 시점이다. 여기에서 dp 개념이 필요하며, 나머지는 백준 2252 줄 세우기 문제의 위상 정렬 접근법을 이용한다.

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

T = int(input())
for test in range(T):
    N, K = map(int, input().split())
    time = list(map(int, input().split()))

    cnt_enter_link = [0] * (N)
    graph = [[] for _ in range(N)]
    dp_build_time = [0] * (N)

    for _ in range(K):
        a, b = map(int, input().split())
        graph[a - 1].append(b - 1)
        cnt_enter_link[b - 1] += 1

    q = deque()
    for i in range(N):
        if cnt_enter_link[i] == 0:
            q.append(i)
    w = int(input()) - 1
    while(q):
        c = q.popleft()
        if c == w:
            print(dp_build_time[c] + time[c])
        for i in graph[c]:
            cnt_enter_link[i] -= 1
            dp_build_time[i] = max(dp_build_time[i], dp_build_time[c] + time[c])
            if cnt_enter_link[i] == 0:
                q.append(i)

image