백준 1068 트리

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

트리 + dfs를 이용하는 문제이다.
n이 최대 50까지라 시간제한에 크게 걸리지 않는다.
최근에 그래프를 배열로 만들어서 푸는 문제가 생각나서 dfs가 아니라 parent배열과 child배열을 만들어서 풀었다.

union-find에서 find 함수를 착안해 문제를 풀었다.
죽인 노드의 parent를 -2로 만들어 주고, 노드들을 돌아가면서 가장 상단의 부모를 찾는 과정에서 -1인 루트노드로 나오면서 자식을 가지지 않는다면 리프노드를 찾을 수 있다.

n = int(input())
parent = list(map(int,input().split()))
k = int(input())
child = [[] for i in range(n)]
for i in range(n):
    if parent[i] != -1:
        child[parent[i]].append(i)
if parent[k] != -1:
    child[parent[k]].remove(k)
parent[k] = -2
def find(node):
    if parent[node] == -1:
        return True
    elif parent[node] == -2:
        return False
    else:
        return find(parent[node])
ans = 0
for i in range(n):
    if find(i) and len(child[i]) == 0:
        ans += 1
print(ans)