[Python/파이썬] 백준 1516번 게임 개발

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

코드

from collections import deque

n = int(input())
times = [0]
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1)
for i in range(n):
    t, *preceded, _ = list(map(int, input().split()))
    times.append(t)
    for building in preceded:
        graph[building].append(i+1)
    indegree[i+1] = len(preceded)

q = deque()
answer = [0]*(n+1)
for i in range(1, n+1):
    if indegree[i] == 0:
        q.append(i)
        answer[i] = times[i]

while q:
    now = q.popleft()
    for nx in graph[now]:
        indegree[nx] -= 1
        answer[nx] = max(answer[nx], answer[now]+times[nx])
        if indegree[nx] == 0:
            q.append(nx)

for i in range(1, n+1):
    print(answer[i])

 

이 문제는 선행되어야 할 건물이 없는 건물부터 짓기 시작해서 선행되어야 하는 건물이 다 지어진 건물이 나올 때마다 순서대로 하나씩 지으면 된다. 

위의 코드를 순서대로 설명해보자면,

1. 입력을 받을 때, i번 건물을 짓는데 걸리는 시간은 times[i]에 저장해두고, 선행되어야 하는 건물은 preceded라는 변수에 저장해두고, 이 건물을 짓고 나서 다음에 지어야 한다는 의미로 선행되어야 하는 건물의 graph[j] 리스트에 i번 건물을 추가해준다. 예를 들어 설명하자면,

 

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

 

이 예시가 있다면 4번 건물은 3번과 1번이 선행되어야 지어질 수 있다. 그러면 graph[3]과 graph[1]의 원소인 리스트에 4를 추가하는 것이다. 

마지막으로 진입차수(=선행되어야 하는 건물 수)를 indegree[i]에 저장한다.

 

2. 진입차수가 0인 건물, 즉 선행하여 지어질 건물이 없는 건물들을 덱(q)에 담고, answer에 이 건물들의 건축 소요 시간을 저장해준다. 여기서 answer[i]에는 i번 건물이 지어지는데 필요한 최소 소요 시간을 저장할 것이다.

 

3. 이제 q의 앞에서부터 하나씩 pop하며 건물을 지어준다. q에 들어왔다는 것은 선행되어야 할 건물이 없거나 다 지어졌다는 뜻이므로 q에서 pop하는 동작을 건물을 짓는다고 이해해도 될 것 같다.

q에서 pop한 빌딩을 now번 건물이라고 할 때, graph[now]를 확인하여 이 건물을 선행되어야 하는 건물로 삼는 건물들을 찾아낸다. 찾아낸 다음 건물들(graph[now])의 indegree를 1씩 감소시키고, answer[nx] 값을 현재 answer[nx]와 지금 지은 건물까지의 전체 소요시간과 nx번 빌딩의 건축 소요 시간의 합(answer[now]+times[nx])을 비교하여 둘 중 큰 값을 answer[nx]에 저장한다. 

 

4. 3번 과정을 q가 빌 때까지 반복하고 나면 answer[1:]에 각 건물을 짓는데 필요한 전체 소요시간이 저장되게 된다. 이 값이 답이다.