백준 : 트리 - 1068

 

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력 1 

5
-1 0 0 1 1
2

예제 출력 1 

2

예제 입력 2 

5
-1 0 0 1 1
1

예제 출력 2 

1

예제 입력 3 

5
-1 0 0 1 1
0

예제 출력 3 

0

예제 입력 4 

9
-1 0 0 2 2 4 4 6 6
4

예제 출력 4 

2

 

여기서 DFS로 접근하여 문제를 풀었다. 이 문제의 핵심으로는 특정 노드와 그 자식 노드 전체를 삭제해야 하기 때문에 DFS는 한 노드에서시작해 재귀적으로 모든 자식 노드를 깊이 우선으로 방문하여 삭제하는 로직을 구현하기에 매우 자연스럽기 때문이다. 또한 그래프 깊이가 길지도 않았고 최단거리도 아니기 때문에 DFS로 필요하지 않는 부분이라면 재귀로 삭제하는 방식이 더 좋지 않을까 생각했다.

 

 

import sys
input = sys.stdin.readline

n = int(input().strip())
tree = list(map(int, input().split()))
delete = int(input())

def dfs(del_node):
    tree[del_node] = -1000
    for i in range(n):
        if del_node == tree[i]:
            dfs(i)
dfs(delete)
cnt = 0
is_parent = set(tree)

for i in range(n):
    if tree[i] != -2 and i not in is_parent:
        cnt += 1
print(cnt)

 

참고 : https://hstory0208.tistory.com/entry/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1068-%ED%8A%B8%EB%A6%AC