[Python] 1516번

1. building_list 에 전부 담는다 
2. 하나씩 확인한다 time(n): n번째 건물의 짓는 시간을 리턴
    i 번째 요소 :
    while 선수 건물 넘버n 확인 -> n 번째 요소의 선수 건물 넘버 k 확인 -> k 번째 요소의 선수 건물 넘버 
    
   for 리스트 돌리기:
    if 선수 건물 x :
           n 번째 요소의 시간 더한다 
    elif 선수 건물 이 요소는 전에 지었다:
			if 이요소가 리스트의 마지막 요소가 아니다 :
             	넘어간다 
            else 이요소가 리스트의 마지막 요소이다:
				더한다.
    else 안지은 건물이 선수 건물이다 :      
      for n 번째 요소의 선수 건물 리스트 하나씩 돌리기 :
        if 선수 건물 x 또는 선수 건물을 이미 지었다 :
             k 번째 요소의 시간 더한다 
		else 안지은 건물이 선수 건물이다 :
               for k 번째 요소의 선수 건물 리스트 하나씩 돌리기 :
        			if 선수 건물 x 또는 선수 건물을 이미 지었다 :
             			k 번째 요소의 시간 더한다 
                     else 안지은 건물이 선수건물이다 :
                         for 

import sys
N= int(sys.stdin.readline())
building_list=[]
for _ in range(N):
   building = list(sys.stdin.readline().split())
   time = int(building[0])
   pre = list(map(int,building[1:-1]))
   building = (time,pre)
   building_list.append(building)

def function(n,i): #n번째 건물 , 그건물의 선수건물 리스트 i
   sum = building_list[n-1][0]
   list =[]
   if len(i)==0:
           return sum
   for k in i:
       if k in list:
           if k != i[-1]:
               continue
           else:
               sum += building_list[k-1][0]
               list.append(k)
               return sum
       else:
           sum += function(k,building_list[k-1][1])
           return sum

for i in range(1,N+1):
   print(function(i,building_list[i-1][1]))

예제코드는 맞는데 틀렸다고 뜬다...

알고리즘 분류가 위상정렬이다!

이미 계산 했던 서브트리를 메모를 해두고 다시 얘를 써두기-> 시간절약
if 0아

1. 방법 : dfs 정렬 ( 재귀적으로 해야하는데 그럼 비효율 적이다 . 그러므로 메모이제이션 기법 )
2. 방법 : 위에서 하나씩 업데이트

트리를 직접 그려서

배운점