백준_1068_트리(해결 못함)

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

1068번: 트리

 

내가 못 푼 이유

> 모르겠음....

 

지금까지의 문제 이해

>한 노드를 지우면 그 노드의 자식 노드들도 다 삭제된다.

>루트노드도 지워질수 있다. ----> 이 경우 첫번째에 말한 이유 때문에 출력값이 0이된다.

>트리는 단 한개만 주어진다.

>이진 트리라는 조건은 문제 설명에 없기 때문에 이진 트리가 아니다.(문제 설명 그림은 이진트리)

삽질의 흔적...

 

코드

import sys, copy

from collections import defaultdict, deque

 

input = sys.stdin.readline

 

num_node = int(input())

node_info = list(map(int, input().split()))

remove_node = int(input())

 

tree = defaultdict(list)

#key == parent node, value == child node

count = 0

for i in node_info:

    if i == -1:

        count += 1

        root_index = node_info.index(i)

        continue

    tree[i].append(count)

    count += 1

 

if remove_node in tree:

    if remove_node == root_index: #루트노드가 지워지면 다 지워지므로 0을 출력한다.

        print(0)

        sys.exit()

    visited = deque()           #한 노드가 지워지면 해당 노드의 자식노드들도 다 지워저야 하므로

    visited.append(remove_node)

    while visited:

        tmp = visited.popleft()

        for i in tree[tmp]:

            visited.append(i)

        del tree[tmp]

 

storage = list()

 

for i in tree:

    if remove_node in tree[i]:

        tree[i].remove(remove_node)

        if len(tree[i]) == 0:

            storage.append(i)

                                

for i in storage:

    del tree[i]

                                #여기까지 노드 삭제!

 

#leaf node check                             

leaf = set()

for i in tree:

    for j in tree[i]:

        if j in tree:

            continue

        leaf.add(j)

'''

'여기까지 노드 삭제!' 바로 위 코드 때문에 부모가 혼자 남는 케이스에서

부모도 삭제해버리기 때문에 len(tree) == 0 ----> 부모가 혼자 남아있는 케이스라 판단

'''

if len(tree) == 0:   

    print(1)

else:

    print(len(leaf))