[SWEA] 5174. subtree - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

< 📝 문제 >
트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아

 

내는 프로그램을 만드시오.

주어지는 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고, 부모가 없는 노드가 전체의 루트 노드가 된다.

이런 경우의 트리는 부모 노드를 인덱스로 다음과 같은 방법으로 나타낼 수 있다. 자식 노드가 0인 경우는 노드가 자식이

 

없는 경우이다.

부모	1	2	3	4	5	6
자식1	6	1	0	0	3	4
자식2	0	5	0	0	0	0

< ❓ 생각 >

트리 만들기 -> 왼쪽자식 넣고, 오른쪽 자식 넣기

자식 노드의 개수 세기! -> 전위 순회로 세기

< 💻 코드 >

def pre_order(v):
    global descendant
    if v:
    	# 노드 수 세기
        descendant += 1
        pre_order(left[v])
        pre_order(right[v])

# 테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # E : 간선의 개수, N을 루트 노드로 하는 서브트리에 속한 노드의 개수 구하기
    E,N = map(int,input().split())
    arr = list(map(int,input().split()))
    # 노드 번호는 1번부터 E+1번까지
    num = E+1
    
    # 왼쪽 자식, 오른쪽 자식
    left = [0] * (num + 1)
    right = [0] * (num + 1)
    for i in range(0, 2 * E, 2):
        # 왼쪽 자식이 없으면 왼쪽에 넣기
        if left[arr[i]] == 0:
            left[arr[i]] = arr[i + 1]
        else:
            right[arr[i]] = arr[i + 1]

    # 자손의 수
    descendant = 0
    pre_order(N)
    print(f'#{tc} {descendant}')