문제설명

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성

리프 노드

트리의 노드 중에서 자식이 없는 최하단의 노드

아이디어 스케치

1. 리스트에 노드의 부모 정보를 저장
2. 지울 노드 큐에 저장
3. 4 지운다 하였을 때, 4를 부모로 가지고 있는 노드 탐색
4. 해당 노드 번호 큐에 저장
5. 큐에서 꺼내서 자식 찾기 반복

틀린코드

N = int(input())
nodes_parent = list(map(int, input().split()))
remove_node = int(input())

remove_nodes_list = [remove_node]
deleted = [False] * N

while(remove_nodes_list):
  node = remove_nodes_list.pop()
  deleted[node] = True
  for x in range(N):
    if nodes_parent[x] == node:
      remove_nodes_list.append(x)

leaf_count = 0
for i in range(N):
  if not deleted[i] and i not in nodes_parent:
    leaf_count += 1

print(leaf_count)

틀린 이유

i not in nodes_parent라는 조건이 "원본 리스트"를 통째로 본다는 점에

• 트리 구조: 0번(부모) -> 1번(자식)
• 리스트 상황: nodes_parent = [-1, 0] (1번의 부모는 0번이라는 뜻)
• 삭제 노드: 1번

1. while문을 돌면 deleted[1]은 True가 됩니다.

2. 이제 마지막 for문에서 i = 0 (0번 노드)을 검사합니다.

3. if not deleted[0] → Pass (0번은 삭제 안 됐으니까요!)

4. if 0 not in nodes_parent → Fail!

   • 왜냐하면 nodes_parent 리스트 안에 0이 들어있거든요. ([-1, 0])

"나를 부모로 가진 녀석이 리스트에 있니?"라고 묻는 대신

"나를 부모로 가진 녀석 중에 '아직 살아있는' 녀석이 있니? 라고 묻기

edge case

3
-1 0 1
2

이유: 2를 지우면 deleted[2]는 True가 됩니다. 하지만 nodes_parent 리스트 안에는 여전히 [ -1, 0, 1 ]이 들어있다.

마지막 루프에서 i = 1일 때, 1 in nodes_parent가 True가 되어버립니다. 1은 실제로는 자식을 잃은 리프 노드인데도, 원본 리스트에 기록이 남아있어서 카운트되지 않는 것.

성공코드

N = int(input())
nodes_parent = list(map(int, input().split()))
remove_node = int(input())

remove_nodes_list = [remove_node]
deleted = [False] * N

while(remove_nodes_list):
  node = remove_nodes_list.pop()
  deleted[node] = True
  for x in range(N):
    if nodes_parent[x] == node:
      remove_nodes_list.append(x)

leaf_count = 0

for i in range(N):
  if deleted[i]: 
        continue
  
  # i를 부모로 가지는 자식들 중, '삭제되지 않은' 자식이 있는지 확인
  has_live_child = False
  for x in range(N):
        if nodes_parent[x] == i and not deleted[x]:
            has_live_child = True
            break
  if not has_live_child:
        leaf_count += 1

print(leaf_count)