SWEA # Python_D3_5178_노드의 합 (tree)

 

🤗 [문제] 

N개의 노드를 갖는 완전 이진 트리의 노드 번호는 루트가 1번이 되며, 같은 단계에서는 왼쪽에서 오른쪽으로 증가, 단계가 꽉 차면 다음단계의 왼쪽부터 시작된다.

완전 이진 트리의 특성상 1번부터 N번까지 빠지는 노드 번호는 없다.

리프 노드의 번호와 저장된 값이 주어지면 나머지 노드에 자식 노드 값의 합을 저장한 다음, 지정한 노드 번호에 저장된 값을 출력하는 프로그램을 작성 하시오.

 

SW Expert Academy

T = int(input())


for tc in range(1, T+1):

    def dfs(idx):
    	# 만약 idx를 벗어난다면 0을 리턴
        if idx > N + 1:
            return 0
        # 만약 노드의 값이 존재한다면 해당 값을 바로 리턴
        if Tree[idx]:
            return Tree[idx]
            
		# 왼쪽 노드 번호를 구하려면 *2
        left = idx * 2
        # 오른쪽 노드번호를 구하려면 *2+1 혹은 왼쪽 노드번호 +1
        right = left + 1
        
        # 재귀호출하여 왼쪽 자식노드의 value값과 오른쪽 자식노드의 value값을 구해준다.
        # 이 둘을 더하면 부모 노드의 value값을 구할 수 있다.
        Tree[idx] = dfs(left) + dfs(right)

        return Tree[idx]
    
	# N : 노드의 갯수
    # M : 리프노드의 갯수
  	# L : 출력할 노드
    N, M, L = map(int, input().split())
    # N+2인 이유 : 만약 N+1로 해준다면 왼쪽노드까지만 존재할 경우 right값에 대한 index자리가 존재하지 않는다.
    # 그래서 index out of range 에러가 발생한다.
    Tree = [0 for _ in range(N + 2)]

    for i in range(M):
        node, value = map(int, input().split())
        
        # Tree에 각 node와 동일한 숫자의 인덱스 자리에 0대신 input받은 value값을 넣어준다
        Tree[node] = value

    result = dfs(L)
    
    print('#{} {}'.format(tc, result))