[백준] 1068 트리

문제

www.acmicpc.net/problem/1068

 

코드

N = int(input())
parents = list(map(int, input().split()))
delete = int(input())

def dfs(delete_node, arr): # delete_node를 부모로 갖는 원소 삭제
    parents[delete_node] = -2
    for i in range(len(parents)):
        if delete_node == parents[i]:
            dfs(i, parents)

def main():
    dfs(delete, parents)
    count = 0
    for i in range(len(parents)): # leaf node 개수 세기
        if parents[i] != -2 and i not in parents:
            count += 1
    print(count)

main()

 

풀이

1. parents 배열에서 delete_node를 부모로 갖는 원소를 삭제한다.
2. parents 배열을 처음부터 끝까지 탐색하며 delete_node가 부모 노드인 인덱스를 찾아 다시 dfs를 재귀호출한다.
3.  dfs 함수 호출이 끝나면, 삭제된 노드들은 모두 -2로 변경되어있으므로 노드가 부모 배열에서 삭제된 노드도 아니고, 다른 노드의 부모 노드도 아니면 count ++ 해주기.