[파이썬/python] 백준 1005 - ACM Craft

문제

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

---

문제 설명

1. ACM 크래프트에서는 매 게임마다 건물을 짓는 순서가 주어진다.
2. 모든 건물은 각각 건설을 시작하여 완성될 때까지 Delay가 존재한다.
3. W번 건물을 짓게되면 게임에서 승리한다.
4. W번 건물을 건설완료하는 데 걸리는 최소 시간을 구해야한다.

 

<예제 1>

 

건설 조건

1. 2번, 3번 건물은 1번 건물이 건설되기 전까지 지을 수 없다.
2. 1번 건물이 건설완료되면 2번, 3번 건물은 동시에 건설할 수 있다.
3. 4번 건물을 짓기 위해서는 2번, 3번 건물이 전부 건설이 완료되어야 한다.
4. 1번 건물을 건설하는 데 10초가 소요된다.

 

2번, 3번 건물을 동시에 건설하므로 4번 건물을 건설하기 위해 걸리는 시간은 총 100초이다.
마지막 4번 건물을 건설하는데 필요한 건물은 10초이다.
따라서 4번 건물을 건설하는데 총 120초의 시간이 소요된다.

---

풀이

특정 번호의 건물을 건설하기 위해서는 선행 건물들을 모두 건설해야 한다. 선행 건물들을 건물 A의 차수로 본다면 건물 A의 차수가 0이될 때, 건물 A를 건설할 수 있다. 따라서 차수가 낮은 노드부터 작업을 수행하는 위상정렬을 생각했다.

1. 건물 건설순서를 입력받을 때 건물의 차수를 같이 입력받는다.
2. 반복문을 통해 차수가 0인 노드를 탐색하고 해당 노드를 Queue에 넣는다.
3. queue에서 차수가 0인 노드(건물)을 꺼내고, 이동할 수 있는 노드들의 차수를 1씩 차감한다.
4. 다음 노드의 차수가 0이되면 해당 건물을 건설할 수 있다는 의미이므로. Queue에 넣는다.
5. 선행 건물들이 모두 건설되어야 다음 건물을 건설할 수 있으므로 선행 건물들 중 건설하는 데 시간이 더 오래 걸리는 것을 고른다.

---

코드

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

for tc in range(int(input())):
    N,K = map(int,input().split())
    costs = [0] + list(map(int,input().split()))
    graph = [[] for _ in range(N+1)]
    degree = [0 for _ in range(N+1)]
    for i in range(K):
        v1,v2 = map(int,input().split())
        degree[v2]+=1
        graph[v1].append(v2)
    W = int(input())
    res = [0 for _ in range(N+1)]
    queue = deque()
    for v in range(1,N+1):
        if degree[v] == 0:
            queue.append(v)
            res[v] = costs[v]



    while queue:
        v1 = queue.popleft()
        tmp = 0
        if v1 == W:
            print(res[W]) 
            break
        for v2 in graph[v1]:
            degree[v2]-=1
            if degree[v2] == 0:
                queue.append(v2)
            res[v2] = max(res[v2], res[v1]+costs[v2])

---

시간복잡도

• 인접그래프를 사용하는 위상정렬의 시간복잡도는 O(V+E)이다.
• 최악의 경우 $V = 10^3, E = 10^5$ 이므로 최악의 경우 약 $O(10^5+10^3) = O(10^5)$의 시간복잡도를 가진다