트리

내 아이디어
1. 부모 노드가 무엇인지를 알려주는 배열을 parent라 하자.
2. paernt_copy배열을 만들어 삭제되는 노드 아래에 있는 노드들(삭제된 노드 자기 자신 포함)의 성분을 모두 -2로 바꿈(삭제됐음을 표시)
3. 삭제된 노드들을 제외, 모든 노드들을 자기 자신을 부모로 가지는 노드가 있는지 검사 (parent_copy배열을 이용하면 된다. 이는 있는지 없는지 검사이므로 set으로 변환해서 검사하면 더욱 최적화된다.)
4. 부모노드를 가지고 있지 않은 노드들의 개수 출력

코드

def isYourParent(x, parent, erase):
   while parent[x] != -1:
        if parent[x] == erase:
           return True
        else:
           x = parent[x]
   return False

def haveChildren(x, parent):
    for k in parent:
        if k == x: return True
    return False

N = int(input())
parent = list(map(int, input().split()))
erase = int(input())
deletedParent = parent[:]

for x in range(N):
    if isYourParent(x, parent, erase):
        deletedParent[x] = -2
deletedParent[erase] = -2

count = 0

for x in range(0,N):
    if not deletedParent[x] == -2:
        if not haveChildren(x, deletedParent):
            count += 1

print(count)

다른 사람 코드
https://www.acmicpc.net/source/38970319
rkaxhdals의 코드

def dfs(cur, leaf):  # cur은 현재 요소, leaf는 leaf노드의 개수
	if not chs[cur]: return leaf + 1  # 비어있는 리스트는 False리턴
	for ch in chs[cur]: leaf = dfs(ch, leaf)
	return leaf

N = int(input())  # 노드의 개수 N
chs = [[] for _ in range(N + 1)]  # 리스트 컴프리헨션
arr = map(int, input().split())  # 어떤 노드의 부모노드를 나타내는 배열  arr
rm = int(input())  # 삭제되어야 하는 노드 아마 remove의 약자인듯하다
root = 0  # root노드

for i, x in enumerate(arr):  # enumerate : 배열의 모든 성분에 대해 인덱스와 성분을 튜플로 같이 리턴
	if x == -1: root = i
	elif i != rm: chs[x].append(i)# i는 자식, x는 부모, 자식이 remove가 아니라면 chs[부모]에 자식 append
    # 여기서 chs는 childrens를 의미함을 알 수 있다

print(dfs(root, 0) if root != rm else 0)  # 삼항연산자, root가 rm이 아니면 dfs(root, 0)을 출력하고 아니면 0을 출력

아이디어 정리

1. 부모 노드를 성분으로 가지는 리스트 arr에 대하여 enumerate를 통해 부모와 자식을 알게됨

2. 자식이 삭제될 노드이면 자식 저장 X -> 부모와 더이상 연결이 안되므로 remove를 루트로 하는 서브트리는 이제 다른 연결요소가 됨 -> dfs로 접근 불가

3. 2.의 과정을 통해 각 노드의 자식노드를 성분으로 하는 이차원 배열을 만듬

4. 이를 dfs로 돌면서 자식 노드가 없을 때마다 leaf의 값을 1 더함.

5. 리프노드의 개수 출력

(예외처리)
1. 만약 부모가 -1이면 이를 root로 삼음
2. dfs(root, 0)인데 root가 삭제되면 자식이 root인 경우가 없어서 코드의 elif에서 걸리지 않으므로 따로 처리

배울 점
1.
iterable한 객체의 성분들에 접근할 때 for i in range 보다는 for x in iterable로

2. enumerate : 배열의 모든 성분에 대해 인덱스의 성분을 튜플로 리턴

3. 리스트 컴프리헨션에 익숙해지자.
   chs = [[] for i in range(N)] -> 비어있는 이차원 리스트 만들기.