SWEA # Python_D2_5174_subtree (tree)

 

🏇 [문제]

트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.

SW Expert Academy

def inorder(node): 
    global cnt
    # 만약 input값이 0이라면 cnt반환
    if node == 0:
        return

    cnt += 1
    
    # 첫 번째 tc를 기반으로 설명하자면
    # 1로 node가 들어오면 cnt가 1 증가하고 inorder(left[node])에서 6의 결과값이 나와
    # 재귀로서 inorder(6)이 실행이 되며 cnt값이 1 더 증가한다.
    # 이는 또 다시 4의 결과값으로 인해 재귀로 inorder(4)가 실행되고 cnt가 1 또 증가한다.
    # 노드 4에는 왼쪽 자식이 존재하지 않아 0의 값이 나오기 때문에 inorder(4)에서 빠져나와
    # inorder(6)으로서 inorder(right[node])이 실행된다.
    # 6은 오른쪽 자식이 존재하지 않아 inorder(6)에서 빠져나오게 되고
    # 이젠 inorder(1)로서 inorder(right[node])이 실행된다.
    # 1역시 오른쪽 자식노드를 가지고 있지 않기 때문에 최종적으로 cnt = 3이 반환된다.
    inorder(left[node])
    inorder(right[node])

 
for tc in range(1, T+1):
    E,N = map(int, input().split())
    arr = list(map(int, input().split()))
    
    # 노드가 1 부터 n 까지일 때 인덱스 0을 무시해주기 위해
    # 노드의 수+1 혹은 간선의 수+2 길이 만큼의 빈 리스트를 만들어 준다.
    left = [0]*(E+2) # 왼쪽 자식노드
    right = [0]*(E+2) # 오른쪽 자식노드

    for i in range(0,len(arr),2): 
        parent, children = arr[i], arr[i+1]
        if left[parent]: # 왼쪽 자식노드에 값이 있다면
            right[parent]=children # 오른쪽 자식 노드에 저장
        else: # 왼쪽 자식노드에 값이 없다면
            left[parent]=children # 왼쪽 자식노드에 저장
 
    cnt = 0
    inorder(N)
    print('#{} {}'.format(tc,cnt))

## 대호님 코드
# 특징 :
# tree = [[0, 0] for _ in range(E+2)] 와 같이 tree리스트를 만들어 주어
# [0]과 [1]로서 왼쪽 자식노드와 오른쪽 자식노드를 구분해주었다.
# tree[node][0] : 왼쪽 자식노드
# tree[node][1] : 오른쪽 자식노드


T = int(input())


def order(node):
    global cnt
    if node == 0:
        return
    cnt += 1
    order(tree[node][0])
    order(tree[node][1])


for tc in range(1, T+1):
    E, N = map(int, input().split())
    nodelist = list(map(int, input().split()))
    tree = [[0, 0] for _ in range(E+2)]

    for i in range(0, len(nodelist), 2):
        parent, child = nodelist[i], nodelist[i+1]
        if tree[parent][0] == 0:
            tree[parent][0] = child
        else:
            tree[parent][1] = child
    cnt = 0
    order(N)
    print("#{} {}".format(tc, cnt))