[Python] SWEA 5174 subtree

SW Expert Academy SWEA 5174 subtree 문제는 주어진 이진트리에서 노드 N을 루트로 하는 트리의 일부인 서브 트리에 속한 노드의 개수를 알아내는 문제이다. tree 트리, binary tree 이진트리 자료구조에 관한 문제로 난이도는 D2다.

 

출처: https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg

 

SW Expert Academy 5174 subtree 문제 정보

자료구조 분류

- tree 트리, binary tree 이진트리

난이도

- D2

 

subtree 문제 요약

• 1번부터 E+1번까지 노드를 갖는 이진트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내 출력한다.(1 <=E <=1000, 1 <=N <=E+1))
• 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고, 부모가 없는 노드가 전체의 루트 노드가 된다.

 

문제 풀이 과정

1. 부모 노드의 번호를 인덱스로, 자식 노드를 값으로 갖는 리스트를 정의한다.
2. 노드 N이 갖는 자식 노드들을 카운트하는 함수를 구현하고 그 자식 노드들이 다시 부모가 되어 자식 노드들을 카운트하는 과정을 재귀 함수를 호출하여 자식 노드가 없을 때까지 반복한다.
3. 자식 노드가 없으면 이때까지 카운트된 개수를 반환한다.
4. 테스트 케이스 번호, 서브 트리에 속한 노드의 개수를 출력한다.

 

코드 및 설명

• tree [][] - 부모 노드의 번호를 인덱스로, 자식 노드를 값으로 갖는 2차원 리스트
• cnt - 서브 트리의 노드의 개수

def subtree(root):
    global cnt
    cnt += 1

    for i in tree[int(root)]:
        if i:
            subtree(i)

    return cnt


for tc in range(int(input())):
    E, N = map(int, input().split())

    nodes = list(input().split())
    tree = [[] for _ in range(E + 2)]
    for t in range(0, len(nodes), 2):
        tree[int(nodes[t])].append(nodes[t + 1])
    cnt = 0
    
    print("#%d %d" % (tc + 1, subtree(N)))

---

SW Expert Academy SWEA 5174 subtree 문제는 tree 트리, binary tree 이진트리 자료구조 활용 문제이며 파이썬으로 구현하였다. 난이도는 D2이다.