악곱 == 악성곱슬

DFS

---

해당 문제는 개인적으로 생각했을때 훼이크가 좀 많은 문제라고 생각했다.

우선 문제를 풀며 지문을 제대로 읽어야 겠다는 생각을 한 부분이

• 이진트리라고 명시되어 있지 않은 경우 자식은 여러개 일 수 있다.
• 꼭 0번 노드가 루트노드가 아닐 수 있다.

위 부분을 놓치고 풀고 있었고 이를 배우는 좋은 계기가 되는 문제였다.

DFS로 푼 이유는, 트리를 깊이우선 탐색을 하며 내가 삭제할 노드를 만나면 하위 노드를 탐색하지 않고 return 하는 방식으로 구현을 하면 되겠다는 아이디어에서 비롯되었다. 코드는 아래와 같다.

구현

---

import sys

def dfs(node, leaf_count, node_to_del):
    if node == node_to_del:
        return leaf_count
    if not tree[node]:
        return leaf_count + 1
    for i in range(len(tree[node])):
        leaf_count = dfs(tree[node][i], leaf_count, node_to_del)
    return leaf_count

def solution(node_to_del):
    leaf_node = 0
    for root in roots:
        leaf_node += dfs(root, leaf_node, node_to_del)
    return leaf_node

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    parent = list(map(int, sys.stdin.readline().rstrip().split()))
    node_to_delete = int(sys.stdin.readline().rstrip())
    tree = [[] for _ in range(N)]
    roots = []
    for i in range(N):
        if parent[i] == -1:
            roots.append(i)
            continue
        if i == node_to_delete:
            continue
        tree[parent[i]].append(i)
    print(solution(node_to_delete))