이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 건물의 순서를 저장하기 위해 인접리스트 방식으로 현재 건물을 짓기 위해 지어야 하는 건물의 번호를 building이라는 리스트로 저장하였다. 그리고 각 건물의 짓는 시간을 time이라는 리스트로 따로 저장하였다.

building리스트가 비어있는 건물은 바로 dp리스트에 값을 time[건물번호]로 갱신하였다. 이는 동시에 여러 건물을 함께 지을 수 있기 떄문이다. 그리고 나서 building리스트와 dp리스트를 이용하여 dp리스트를 완성해야 한다.

처음에는 building[현재 건물번호]를 순회하며 해당 dp의 값 중 가장 큰 값을 더하는 방식으로 진행하였다. 그러나 이럴 경우, 데이터가 입력될 때, 아직 정의되지 않은 건물을 먼저 지어야 하는 경우가 있다면 제대로된 값을 출력해낼 수 없다. 이에 대한 접근법을 다시 생각하였고, 재귀 함수를 이용하면 해결될 것이라 생각하였다.

building[cur]을 순회하며 만약 dp[before]가 0일 경우(아직 정의되지 않았을 경우), 이 함수를 재귀호출하여 먼저 정의되어야 하는 건물의 dp를 먼저 정의하는 방식이다. 시간을 줄이기 위해 함수 호출 전에 조건문으로 dp[i]가 정의되지 않았을 경우에만 함수를 호출할 수 있도록 하였다.

Code

n = int(input())
building = [[] for _ in range(n+1)]
time = [0 for _ in range(n+1)]
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = list(map(int, input().split()))
    time[i] = tmp[0]
    if len(tmp) == 2:
        dp[i] = time[i]
        continue
    for j in range(1, len(tmp)-1):
        building[i].append(tmp[j])
def dfs(cur):
    mx = 0
    for before in building[cur]:
        if dp[before] == 0:
            dfs(before)
        mx = max(mx, dp[before])
    dp[cur] += mx+time[cur]
for i in range(1, n+1):
    if dp[i]:
        continue
    else:
        dfs(i)
for i in range(1, n+1):
    print(dp[i])