⭐⭐⭐⭐[코드트리] 트리 노드 제거

https://www.codetree.ai/missions/9/problems/remove-tree-node/description

 

문제 

 

트리가 하나 주어집니다.

이 트리에서 노드를 하나 지우려고 합니다. 트리에서 특정 노드를 지우는 경우에, 그 트리의 모든 자손이 같이 지워집니다.

지워진 이후의 트리에서의 리프 노드(자식노드가 없는 노드)의 개수를 구하는 프로그램을 작성해보세요.

 

입력 형식 

 

첫 번째 줄에서 트리 노드의 개수 n이 주어집니다.

두 번째 줄에는 0번 노드부터 n-1번 노드까지, 부모 노드의 번호가 주어집니다.

부모 노드가 없는 루트 노드의 경우에는, -1이 대신 주어집니다.

세 번째 줄에는 지울 노드의 번호가 주어집니다.

• 1 ≤ n ≤ 50

출력 형식

첫 번째 줄에 입력으로 주어진 트리에서 노드를 제거하였을 때, 지워진 이후의 트리에서의 리프 노드의 개수를 출력합니다.

 

입출력 예제

예제1

입력:

5
-1 0 0 1 1
1

 

출력:

1

 

---

DFS를 이용하여 트리를 순회한다

 

DFS를 이용하여 트리 순회를 진행한다.

삭제된 노드를 별도로 표시하여 탐색 도중 삭제된 노드를 만나면 더 깊이 탐색하지 않는 식으로 구현이 가능하다.

탐색 도중 특정 노드에 대해 추가로 탐색할 노드가 없는 경우라면 이 노드는 리프 노드(자식이 없는 노드)임이 분명하기에 답을 갱신해 주면 된다. 

따라서 이 풀이의 시간 복잡도는 트리 순회에 드는 시간복잡도인 O(N)이 된다. 

 

import sys
sys.stdin=open('input.txt', 'r')

# DFS를 통해 x 아래의 리프노드의 개수를 찾아줍니다.
def DFS(x):
    global ans
    
    if is_deleted[x]:   # (루트 노드가 삭제되었을 때) 삭제된 노드는 스킵합니다.
        return

    # x번 노드가 리프노드인지 판단합니다. 자신의 자식 노드가
    # 하나라도 남아 있을 경우 x번 노드는 리프노드가 아닙니다.
    is_leaf = True
    if len(graph[x]) != 0:      # 연결된 자식 노드가 하나이상 있으면 
        for y in graph[x]:
            # 삭제된 노드는 스킵합니다.
            if is_deleted[y]: 
                continue
            DFS(y)

            is_leaf = False

    # 연결된 자식 노드가 없는 즉, 리프 노드 이면 
    if is_leaf: 
        ans += 1

if __name__=="__main__":
    n = int(input())
    par = list(map(int, input().split()))   # n개의 간선 정보를 입력받습니다.
    target = int(input())   # 제거할 노드 

    root = -1
    graph = [[] for _ in range(n)]
    is_deleted = [False] * (n)

    for x,y in enumerate(par):
        if y == -1:         # -1이 입력된 경우 루트 노드로 지정합니다.
            root = x        # root는 0번째 노드 
            continue
        graph[y].append(x)  # 간선 정보를 인접리스트에 넣어줍니다.

    # 노드를 제거하는 방법에는 간선을 직접 끊어주는 등 여러 방법이 있습니다.
    # 여기서는 삭제되었는지 여부를 배열로 관리합니다.
    is_deleted[target] = True   # 일단 제거할 노드부터 삭제 

    ans = 0
    DFS(root)   # root 정점으로부터 리프노드의 개수를 찾습니다.
    print(ans)