1005. ACM Craft (Python)

1005번: ACM Craft

 

풀이

 건물을 짓는 것에 순서가 존재한다. 즉, 방향성이 존재하는 그래프 형태로 표시할 수 있고 그래프에 사이클이 존재하지 않기 때문에 위상정렬을 이용하여 문제를 해결할 수 있다.

 

 각 건물을 지으며 다음으로 지을 수 있는 건물의 진입 차수를 하나씩 낮추면서 다음 건물의 걸리는 시간을 업데이트 해주면 된다. 이 때, 업데이트 되는 시간은 가장 오래 걸리는 시간으로 해주어야 한다. 예를 들어 문제의 예제를 살펴 보자.

 

 일단 처음에 1번 건물을 지으며 10초가 걸린다. 1번 이후에 지을 수 있는 건물인 2와 3번 건물은 진입 차수가 0이 되어 새롭게 큐에 들어간다.

 

 처음 2번 건물을 지을 때 4번 건물의 진입 차수는 줄어들지만 아직 진입 차수가 1이기 때문에 큐에는 들어오지 못한다. 하지만 큐에 들어오는 것과 상관없이 기존의 4번 건물 건설 시작 시간과 2번 건물 건설 완료 시간을 비교하여 4번 건물을 짓기 시작하는 시간을 업데이트 한다(처음 기본 값은 0이기 때문에 11이 더 커서 11로 설정된다).

 

 다음 3번 건물을 지을 때 드디어 4번 건물의 진입 차수가 0이 되어 큐에 들어오게 된다. 이때 3번 건물 건설 완료 시간(10 + 100)과 기존의 4번 건물 건설 시작 시간(11)을 비교하여 업데이트 한다(110으로 업데이트).

 

 이제 마지막으로 4번 건물을 큐에서 꺼내고 건설 시작 시간인 110초에 4번 건물 건설 시간인 10초를 더한 값을 반환하도록 한다.

 

 

코드

import sys

input = sys.stdin.readline


def solve():
    N, K = map(int, input().split()) # N: 건물의 개수, K: 건물의 건설순서 규칙의 개수
    buildTimes = [0] + list(map(int, input().split())) # 건물당 건설에 걸리는 시간 
    times = [0 for _ in range(N+1)] # 각 건물의 건설 시작 시간 
    graph = [[] for _ in range(N+1)] # 건설순서 그래프
    indegree = [0 for _ in range(N+1)] # 각 건물의 진입 차수 

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

    W = int(input())  # 승리하기 위해 건설해야 하는 건물의 번호

    q = [] # 진입차수가 0인 건물을 넣는 큐 

    # 처음 전체 건물을 살펴서 진입차수가 0인 건물을 큐에 넣는다.
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        curBuilding = q.pop(0) # 현재 짓는 건물 

        # 현재 건물의 건설 완료 시간 = 현재 건물의 건설 시작 시간 + 현재 건물의 건설에 걸리는 시간 
        completeTimes = times[curBuilding] + buildTimes[curBuilding]

        if curBuilding == W: # 건설해야 하는 건물의 번호에 도달했으면 건설 완료 시간을 반환하여 종료 
            return completeTimes

        # 현재 건물 이후에 지을 수 있는 건물에 대하여 
        for nextBuilding in graph[curBuilding]:
            indegree[nextBuilding] -= 1 # 진입 차수 감소

            # 다음 건물의 건설 시작 시간 = '기존 건설 시작 시간'과 '현재 건물 건설 완료 시간'중 더 오래 걸린 시간으로 설정 
            times[nextBuilding] = max(times[nextBuilding], completeTimes)

            if indegree[nextBuilding] == 0: # 이제 지을 수 있는 건물에 해당하면
                q.append(nextBuilding) # 큐에 삽입 


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        print(solve())