내 아이디어
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을 출력
아이디어 정리
부모 노드를 성분으로 가지는 리스트 arr에 대하여 enumerate를 통해 부모와 자식을 알게됨
자식이 삭제될 노드이면 자식 저장 X -> 부모와 더이상 연결이 안되므로 remove를 루트로 하는 서브트리는 이제 다른 연결요소가 됨 -> dfs로 접근 불가
2.의 과정을 통해 각 노드의 자식노드를 성분으로 하는 이차원 배열을 만듬
이를 dfs로 돌면서 자식 노드가 없을 때마다 leaf의 값을 1 더함.
리프노드의 개수 출력
(예외처리)
1. 만약 부모가 -1이면 이를 root로 삼음
2. dfs(root, 0)인데 root가 삭제되면 자식이 root인 경우가 없어서 코드의 elif에서 걸리지 않으므로 따로 처리
배울 점
1.
iterable한 객체의 성분들에 접근할 때 for i in range 보다는 for x in iterable로
enumerate : 배열의 모든 성분에 대해 인덱스의 성분을 튜플로 리턴
리스트 컴프리헨션에 익숙해지자.
chs = [[] for i in range(N)]
-> 비어있는 이차원 리스트 만들기.