[백준 1516] 게임 개발(python)

1516번: 게임 개발

---

 

위상정렬을 사용하자!

 

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

arr 배열: i행은 i건물의 재료건물들을 나타내고, i열은 i건물이 재료가 되는 건물들을 나타낸다.

 

1. 입력을 받으면서 필요한 재료건물을 arr배열에 기록하고, 진입차수(indegree)를 update해준다.
2. 진입차수가 0이라면 필요한 재료들을 다 만들어졌다는 뜻으로 queue에 넣어준다.
3. queue를 돌면서 건물을 완성할때 해당 건물이 재료가 되는 건물 진입차수를 1 줄여준다.
4. 재료건물들은 동시에 여러개 생성할 수 있으므로 제일 오래 걸리는 재료건물시간을 더해준다.

 

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

N = int(input())
queue = deque()
indegree = [0]*(N+1)
arr = [[0]*(N+1) for _ in range(N+1)]
time = [0]*(N+1)

for i in range(1, N+1):
    _input = list(map(int, input().split()))
    time[i] = _input[0]
    for x in _input[1:-1]:
        arr[i][x] = 1
        indegree[i] += 1

for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    x = queue.popleft()
    t = 0
    for i in range(1, N+1):
        if arr[i][x] == 1:
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)
        if arr[x][i] == 1:
            t = max(time[i], t)
    time[x] += t

for i in time[1:]:
    print(i)