[SWEA] subtree (python)

SWEA Learning Club Tree 6차시 문제

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

SW Expert Academy

Subtree 문제

트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 세는 문제

처음 Tree를 접하면 생각해내는게 쉽지 만은 않은 문제

100% 내 생각으로 풀었는가?
→ X

트리의 개념은 알겠는데, 이걸 코드로 어떻게 구현해야하는지 애먹다가 교수님께서 공유해주신 슈도코드를 보고 해결해낸 문제

내가 푼 정답코드

def order(i):
    global cnt
    if i == 0:
        return
    cnt += 1 #노드 갯수
    order(left[i])        # 왼쪽 자식으로 이동
    order(right[i])       # 오른쪽 자식으로 이동

T = int(input())
for case in range(1,T+1):
    E, N = map(int, input().split())
    arr = list(map(int, input().split()))
    cnt = 0
    V = E + 1
    left = [0] * (V+1) #왼쪽 자식
    right = [0] * (V+1) #오른쪽 자식

    for i in range(E):
        p, c = arr[i*2], arr[i*2+1]
        if left[p] == 0:
            left[p] = c
        else:
            right[p] = c
    order(N)
    print(f'#{case} {cnt}')

생각보다 간단하면서도 100% 직접 생각해내라 하면 어려움이 많은거같다.

재귀를 활용하여 왼쪽과 오른쪽 자식을 찾아 체크해가면서 갯수를 늘려가는게 중요한 문제

---

느낀점

트리를 접하고 처음으로 풀게된 트리와 관련된 문제. 처음에는 어차피 그래프 개념과 유사하니 BFS로 해결하면 되겠지 생각했으나 생각보다 원하는 값이 안나와서 애먹었다. 트리 개념을 코드로 찾아보면 대부분 class로 구현한 내용뿐이라 알고리즘 문제를 해결하는데 사용하기엔 어려움이 많았기에 풀어내는거에 더 어렵게 느꼈던거 같다.

그래도 트리 문제를 이런식으로 접근하면 된다 하고 배운 문제!