[BOJ/백준] 1068 트리

N = int(input())

arr = list(map(int,input().split()))
parent = {i:[] for i in range(N)}
child = {i:[] for i in range(N)}
root_node = -1
for ind in range(N):
    if arr[ind] == -1:
        root_node = ind
    else:
        parent[ind].append(arr[ind])
        child[arr[ind]].append(ind)
remove_node = int(input())
if root_node != remove_node:
    remove_nodes = set()
    stack = [remove_node]
    visited = [True] * N
    while stack:
        node = stack.pop(0)
        remove_nodes.add(node)
        for k in child[node]:
            if visited[k]:
                visited[k] = False
                stack.append(k)
        parent_node = parent[node][0]
        child[parent_node].remove(node)

    leef_nodes = set()

    for ind in range(N):
        if not len(child[ind]):
            leef_nodes.add(ind)
    print(len(leef_nodes-remove_nodes))
else:
    print(0)

가장 자신없고, 공부를 많이 안한 Tree 분야라, 코드가 난잡하다. 기본적인 원리는 parent_node들과 child_node들을 정리해주고, root_node를 구해준다.

만약 지워야할 remove_node와 root_node가 같을시 leafnode가 없으니 0을 출력해준다.

 

그 외에는 다음과 같이 진행을 한다. 지워진 node들과 leafnode가 될수 있는 node들을 구한뒤 leafnode에서 remove_node를 차집합을 해줘서 그 길이를 출력해준다. 이게 가능했던 이유는 , 반복문을 돌면서 remove_node로 들어간 node들의 child_node를 빼줬기 때문이다.

 

내가 푼 풀이는 난잡하게 여러 변수들이 존재하고, 깔끔하지 못해서 잘 푸신 다른분의 코드를 클론코딩하면서 공부도 했다.

 

 

---- 클론 코딩 및 분석---

# nh7881님 코드 분석

def find_leafs(index,child_nodes):
    # index가 -1이라는 것은 root_node가 remove_node인 경우이니, 그때에는 0을 반환을 해준다.
    if index == -1:
        return 0
    # child_node의 길이가 0인것은 child_Node가 없는 것이므로, leaf_node이다 그러므로 1을 반환해준다.
    if len(child_nodes[index]) == 0:
        return 1
    result = 0
    # 현재 노드인 index의 child_node를 가져와서, 재귀를 실행시켜준다.
    for child_node in child_nodes[index]:
        result += find_leafs(child_node,child_nodes)
    return result



N = int(input())
graph  = list(map(int,input().split()))
# 최상위 노드를 찾아주기 위함이다. 초기값은 node에 존재하지 않는 값으로 해준다.
root_node = -1
remove_node = int(input())
child_nodes = {i:[] for i in range(N)}

for ind in range(N):
    # 우리는 leaf_node를 찾을것이고, 해당 index에 부모 node로 들어온 
    # input값을 반대로 바꿔주는 과정이 필요하다.
    # 만약에 지우는 node와 index가 같으면 굳이 parent을 찾아 child를 넣어주는 과정이 필요없다.
    # 그래서 continue로 넘어가준다.
    # 또한 유일하게 부모가 없는 root_node는 따로 구분을 해준다. if문의 순서가 remove_node가 먼저 앞으로
    # 오는 이유는 remove_node가 root_node일수 있기 때문이다. 이럴때를 구분해주기 위해, remove_node인지 판별하는게 먼저온다.
    # 그외에는 전부 parent_node를 기준으로 child를 추가해주는 방식으로 해준다.
    if remove_node == ind:
        continue
    if graph[ind] == -1:
        root_node = ind
        continue
    child_nodes[graph[ind]].append(ind)

# root_node를 기점으로 leaf_node를 찾는 재귀함수를 실행시켜준다.
print(find_leafs(root_node,child_nodes))