[백준] 1068번 : 트리

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

1068번: 트리

자기자신으로부터 방문할 수 있는 노드를 graph의 배열에 넣어둔뒤, 루트노드로부터 자식 노드들을 방문해가면서 각각의 노드들의 자식노드가 0일경우 cnt값을 증가시켜 문제를 해결 하였습니다.

루트노드가 지워진 노드일경우는 트리 자체가 사라지기 때문에 0으로 예외사항을 추가 했습니다.

N = int(input())
nodeInput = list(map(int ,input().split()))
deletedNode = int(input())
graph = [[] for _ in range(N)]
rootnode = 0
for i in range(len(nodeInput)):
    if nodeInput[i] >= 0:
        graph[nodeInput[i]].append(i)
    else:
        rootnode = i
    
cnt = 0

def leafNode(node):
    global cnt
    childnode_cnt = len(graph[node]) # 자식노드 개수 init
    for childnode in graph[node]:
        if childnode != deletedNode: # 지워진 노드가 아니라면
            if leafNode(childnode) == 0:
                cnt += 1
        else: # 지워진 노드라면
            childnode_cnt -= 1 # 해당노드를 자식에서 지운다.
    
    return childnode_cnt

if leafNode(rootnode) == 0:
    cnt += 1

if rootnode == deletedNode: # 루트노드가 지워진 노드 예외 처리
    print(0)
else:
    print(cnt)