SWEA 학습 동아리 트리 문제 6차
SW 전문가 아카데미
SW 프로그래밍 능력 강화에 도움이 되는 다양한 학습 콘텐츠를 확인하세요!
swexpertacademy.com
![[SWEA] subtree 1](https://blog.kakaocdn.net/dn/EibgT/btr0p7dsrQv/E0uzjDgPMW7nEKh9tYBce1/img.png)
하위 트리 문제
트리의 노드 N에 뿌리를 둔 하위 트리의 노드 수를 계산하는 문제
트리를 처음 만났을 때 찾기 쉽지 않은 문제
제 생각으로 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% 혼자 개발하라고 하면 많이 어려울 것 같습니다.
중요한 문제는 재귀를 사용하여 왼쪽 및 오른쪽 자식을 찾고 확인하는 동안 개수를 늘리는 것입니다.
나는 그것을 느꼈다
첫 번째 트리를 찾아 해결한 것과 관련된 문제입니다.
처음에는 Graph 개념과 비슷해서 BFS로 해결이 가능할 줄 알았는데 원하는 값을 얻지 못해서 애를 먹었습니다.
코드에서 트리 개념을 찾아보면 대부분 클래스로 구현된 것 같아서 알고리즘 문제를 풀기 위해 사용하는 것이 더 어려워 보였다.
그런데 제가 배운 문제는 트리 문제를 이렇게 접근할 수 있다는 것이었습니다!