★Tree Advanced I - 1 Solved★

★ 1068 트리 ★

 

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
tree=[[] for _ in range(N)]
visited=[[] for _ in range(N)]
start_node = 51
ans = 0

def dfs(tree, visited, delete_node, start_node):
    global ans
    visited[start_node] = True
    if len(tree[start_node]) == 0: #leaf-node
        ans += 1
    else:
        len_child = len(tree[start_node])
        if len_child == 1: #one child node
            child = tree[start_node][0]
            if child == delete_node: #one child is trimmed -> node itself will be leaf-node
                ans+=1
            else:
                dfs(tree, visited, delete_node, child)
        else: #two child nodes
            for v in tree[start_node]:
                if v != delete_node:
                    dfs(tree, visited, delete_node, v)

for child_node in range(len(l)):
    parent_node = l[child_node]
    if parent_node == -1:
        start_node = child_node
    else:
        tree[parent_node].append(child_node)

delete_node=int(input())

if delete_node == start_node:
    print(0)
else:
    dfs(tree, visited, delete_node, start_node)
    print(ans)

 

🌲 tree graph 만들기 → root node(-1일 때) start node로 찾기

 

🌲

① 시작 노드가 곧 삭제할 노드라면 노드 아예 없으므로 0 출력

 

② 위 ①이 아니라면 dfs 시작

* leaf-node 판별법

→ 자식 노드의 개수가 0일 경우 해당 노드는 leaf-node →  따라서 바로 전역변수 ans+=1 

 

→ 자식 노드의 개수가 1일 경우

(1) 자식 노드가 삭제할 노드라면 해당 노드는 leaf-node → 전역변수 ans+=1

(2) 삭제할 노드가 아니라면 dfs 시작

 

→ 자식 노드의 개수가 2일 경우 삭제할 노드가 아닌 자식 노드라면 dfs 시작

 

🌲 dfs를 돌되, 삭제할 노드가 딱 1개가 있으므로 이 부분만 주의해서 if문에 맞게 dfs 돌면서 leaf-node 개수 세어주는 유형

child node의 개수와 delete node가 child node인지에 따라 5가지 case로 나눌 수 있다

---