[ 백준 / 골드3 / 파이썬 Python ] 1516번 - 게임 개발

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

1516번: 게임 개발

 

코드

---

from collections import defaultdict,deque

n = int(input())
time = [0] * (n+1)
count = [0] * (n+1)
preq = defaultdict(list)

q = deque()
for i in range(1,n+1):
    arr = list(map(int,input().split()))
    time[i] = arr[0]
    for x in arr[1:-1]:
        preq[x].append(i)
        count[i] += 1
    if count[i] == 0:
        q.append(i)

ans = time.copy()
while q:
    #print(ans)
    x = q.popleft()
    for y in preq[x]:
        count[y] -= 1
        ans[y] = max(ans[y],time[y]+ans[x])
        if count[y] == 0:
            q.append(y)

print(*ans[1:],sep='\n')

 

사용 알고리즘

---

위상정렬 + DP

 

풀이

---

특정 건물을 지어야 지을 수 있는 건물이라는 조건을 보면 위상정렬을 사용해야 한다는 것을 알 수 있었고 그 건물들을 짓는데 드는 시간들이 존재한다는 것에서 DP가 필요하다고 생각했다.

 

먼저 문제에 나온 예시를 살펴보자.

3번 건물을 짓는데는 1번 건물이 필요하고, 4번 건물을 짓는데에는 3번과 1번 건물이 필요하다. 3번 건물을 지을 때에도 1번 건물이 필요하므로 4번 건물은 사실상 3번 건물만 지으면 지을 수 있지만 문제에는 그런 친절한 설명을 주지 않는다. 이 중복될 수 있는 시간을 없애는 것이 이 문제의 키포인트이다.

 

이 부분을 해결하는 코드는 다음과 같다.

동시에 지을 수 있는 건물의 수에 제한이 없기 때문에 한 건물을 지을 때 필요한 시간은 그 건물이 필요한 건물들 중 가장 오래 걸리는 시간이다.

위의 예시를 보면 4번 건물을 짓기 위해서는 1번과 3번 건물이 필요한데 3번 건물은 1번 건물+3번 건물의 기본시간이기 때문에 3번 건물이 더 오래 걸린다. 따라서 3번 건물을 짓는 시간만 고려한다면 3번 건물을 짓기 위해 사용해야할 시간을 모두 무시해줄 수가 있다.