백준 1516

<게임 개발하기>

난이도 : 골드 3

1. 백준 문제
   1516

2. 코드 알고리즘

• 현재 건물을 짓는데 필요한 부모 건물
  부모 건물을 다 건설한 후에 자신 건물을 지을 수 있다

  ex. 2번 건물은 1번 건물을 지은 '후'에 2번 건물을 지을 수 있음
  따라서 10+10= 20초 걸림

• 현재 건물을 짓는데 필요한 부모 건물이 여러개일 경우
  여러개의 건물을 동시에 지을 수 있다는 점을 주의해야 한다.

  ex. 4번 건물은 3번 건물(14초), 1번 건물(10초)를 짓고 지을 수 있다. 
  하지만, 동시에 여러 건물을 지을 수 있으므로 14초 + 10초 + 4초 가 아닌! 
  14초(3번 건물과 1번 건물중 오래 소요되는 시간) + 4초 = 18초 이다

=> 이 2가지가 핵심이라 생각됨

3. 코드

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

import sys
input = sys.stdin.readline

N = int(input())
 A = [[] for i in range(N+1)]
indegree = [0]*(N+1)
selfBuild = [0]*(N+1)
answer = [0]*(N+1)

for i in range(1, N+1):
    a = list(map(int, input().split()))
    for j in range(1, len(a)-1):
        A[a[j]].append(i) #인접 리스트 데이터 저장
        indegree[i] += 1 # 진입 차수 리스트 데이터 저장
    selfBuild[i] = a[0] # 자기 자신 시간 리스트 데이터 저장
    answer[i] = a[0]

from collections import deque
queue = deque()

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

while queue:
    now_node = queue.popleft()
    for i in A[now_node]:
        indegree[i] -= 1
        answer[i] = max(answer[i], answer[now_node]+selfBuild[i])

        if indegree[i] == 0:
            queue.append(i)

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

4. 코드 후기
   그냥 슈도 코드를 보고 한글어를 파이썬으로 바꾼 것밖에 하지 않음...
   어려웠음 ...

• 우선 문제를 제대로! 완벽히! 이해하는 것이 중요하다
  여러 건물을 동시에 지을 수 있다는 점 & 인접리스트 구성
  당연하게 가리키는 원소가 먼저 와야 되는 게 아닐까.... 먼저 시행되어야 되는 원소를 화살표의 꼬리로 두자! 그리고 화살표의 꼬리가 인접리스트의 부모노드!

  많이 부족하고 또 많이 부족하네요