문제
트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.
주어지는 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고, 부모가 없는 노드가 전체의 루트 노드가 된다.
이런 경우의 트리는 부모 노드를 인덱스로 다음과 같은 방법으로 나타낼 수 있다. 자식 노드가 0인 경우는 노드가 자식이 없는 경우이다.
[입력]
첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 첫 줄에 간선의 개수 E와 N이 주어지고, 다음 줄에 E개의 부모 자식 노드 번호 쌍이 주어진다.
노드 번호는 1번부터 E+1번까지 존재한다. 1<=E<=1000, 1<=N<=E+1
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
풀이
잘 해결되지 않아 구글링 해보았다.
이진트리 이므로 노드에 index값에 따른 left,right요소가 있다 생각하고
left와 right 리스트를 만들어준다. 입력값을 저장시킨 후 count라는 함수를 만들어서 재귀함수를 구성한 후 count함수가 호출될때마다 cnt값을 1씩 증가시킨다.
count(0)일때는 return을 해주면된다.
예를들어 count(5)이면 5에는 자식노드가 3 하나뿐이므로 count(3),count(0)이 호출되고 count(3)은 자식노드가 없으므로 count(0),count(0)이 호출되는데 count(5),count(3)호출시 각각 cnt+=1이 되어 cnt=2가 되고, count(0)들은 아무런 일도 일어나지 않는다.
코드
def count(idx):
global cnt
if idx == 0:
return
cnt += 1
count(left[idx])
count(right[idx])
T = int(input())
for test_case in range(1, T+1):
E, N = map(int,input().split())
datas = list(map(int, input().split()))
left = [0] * (E + 2)
right = [0] * (E + 2)
cnt = 0
for i in range(0, len(datas), 2):
index = datas[i]
value = datas[i+1]
if left[index]:# left에 값이 있으면
right[index] = value
else: #비어있으면
left[index] = value
count(N)
print(f'#{test_case} {cnt}')아직 재귀라는 개념을 받아들이기가 많이 어렵다 공부를 더 많이 해야겠다.
