Baekjoon 1005. ACM Craft / Python

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

알고리즘 설명

문제 설명

건물의 개수가 주어지고, 어느 건물이 지어지기 전에 지어져야 하는 건물들의 정보가 주어진다.
이를 활용해서 최단 시간 내 목표 건물을 지어야 한다.

코드 설명

현재 건설할 수 있는 건물 ( 선행건물이 없거나, 이미 지어진 건물)을 큐에 추가한다.

큐에서 하나씩 꺼내어 건물을 짓는 과정을 수행한다.

이 때, 그 건물이 선행 조건에 해당하는 건물인 경우 목록에서 제거하고, 시간을 최신화 해준다.

트리의 노드들을 순서대로 나열하는 위상 정렬방식을 사용하여 간선의 순서가 항상 올바르게 작동할 수 있도록 한다.

큐에서의 각 노드 처리, 간선 리스트를 처리하므로 시간 복잡도와 공간복잡도는 모두 O(n + k)가 된다.

from collections import deque as dq 
T  = int(input())  # 테스트 케이스

for _ in range(T):
    # 건물의 수와 건설 규칙의 수
    n, k = map(int, input().split())
    
    # 각 건물의 건설 시간
    spend_time = [0] + list(map(int, input().split()))
    
    # 건물 간의 건설 순서 규칙을 저장할 리스트
    need = [[] for _ in range(n + 1)]
    
    # 건설 순서 규칙 입력
    for i in range(k):
        x, y = map(int, input().split())
        need[y].append(x)  # y를 건설하기 위해서는 x를 먼저 건설해야 함
    
    # 목표 건물 번호
    w = int(input())
    
    # 큐를 초기화하고, 각 건물의 총 건설 시간을 저장할 리스트를 초기화
    q = dq()
    total_time = [0] * (n + 1)

    # 건설할 수 있는 건물을 큐에 추가
    for i in range(n + 1):
        if not need[i]:
            q.append(i)
            total_time[i] = spend_time[i]
    
    # 큐가 빌 때까지 반복
    while q:
        now = q.popleft()  # 큐에서 건물을 하나 꺼냄
        time = total_time[now]  # 현재 건물의 총 건설 시간
        
        # 현재 건물에서 건설할 수 있는 다음 건물들을 확인
        for i in range(1, n + 1):
            if now in need[i]:  # 현재 건물이 i 건물의 선행 조건이라면
                need[i].remove(now)  # 현재 건물을 i의 필요 목록에서 제거
                if not need[i]:  # i의 모든 선행 건물이 완료되었다면
                    q.append(i)  # i를 큐에 추가
                total_time[i] = max(total_time[i], time + spend_time[i])  # 건설 완료까지의 시간 업데이트

    # 목표 건물의 건설 완료 시간을 출력
    print(total_time[w])