백준 1068

<리프노드 개수 구하기>

난이도 : 골드 5

1. 백준 문제
   1068

2. 코드 알고리즘

• 트리
  트리 구조

• 1068 알고리즘

3. 코드

#1068
#https://www.acmicpc.net/problem/1068

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
a = list(map(int, input().split()))
del_node = int(input())

#인접리스트 작성하기
cs = [[] for _ in range(N)]
for i in range(len(a)):
    if a[i] == -1:
        continue
    else:
        parent_node = a[i]
        cs[parent_node].append(i)

def DFS():
    while queue:
        now = queue.popleft()
        for i in cs[now]:
            del_list.append(i)
            queue.append(i)

#노드 삭제하기
#DFS 이용해 모든 자식 노드 삭제하기
queue = deque()
queue.append(del_node)
del_list =[]
del_list.append(del_node)

DFS()
for i in range(len(del_list)):
    cs[del_list[i]] = [-1] #-1은 del을 의미

#del 노드를 자식노드로 가진 경우!
for i in range(len(del_list)):
    node = del_list[i]
    for j in range(N):
        if node in cs[j]:
            cs[j].remove(node)

result = 0
if N != 1:
    for i in range(N):
        if len(cs[i]) == 0: #자식노드가 없을 경우 리프노드이므로
            result+=1
else:
    result = 0
print(result)

3-1. 반례

• 리프노드가 0개인 경우

#반례 1
1
-1
0

• 제거노드를 자식노드로 가질 경우 (76%에서 틀릴경우)
  반례 주소

#반례 2
2
-1 0
1

#반례 3
9
-1 0 0 5 2 4 4 6 6
4

• 첫번째 주어진 노드가 루트노드가 아닌 경우

#반례 4
6
1 2 3 4 -1 4
5

• (내 코드의 경우) del 노드의 인접리스트의 자식노드 값을 [0]으로 설정
  하지만 이럴 경우 루트노드 [0]과 중복 발생!
  -> del 노드의ㅣ 자식노드값을 [-1]로 변경

4. 코드 후기
   반례 처리하느라 갈렸다,,,