[백준 파이썬] 1068 트리

 

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

1068번: 트리

문제



 

주어진 트리의 한 부분을 제거했을 때, 해당 트리의 리프노드의 개수를 출력하는 문제이다.

---

풀이

노드의 리프노드를 확인하는 문제이므로 DFS를 사용하였다.

 

N = int(input())

node = list(map(int, input().split()))

delete = int(input())

먼저 노드의 정보와 지울 노드의 번호를 입력받는다.

 

def DFS(num, arr):
    arr[num] = -2
    for i in range(len(arr)):
        if num == arr[i]:
            DFS(i, arr)

DFS의 구현은 다음과 같다.

먼저 지울 노드의 번호와 해당 노드의 정보를 입력받는다.

이후 지울 노드의 정보를 -2로 바꾼 후 노드를 순회하면서 해당 노드의 부모노드가 지울 노드일 경우 DFS를 재귀한다.

 

이렇게 되면 최종적으로 지울 노드의 모든 자식노드의 정보가 -2가 된다.

 

DFS(delete, node)

for i in range(len(node)):
    if node[i] != -2 and i not in node:
        count += 1

print(count)

출력은 노드의 정보가 -2가 아니면서 i값이 node에 있지않은경우 count를 증가시킨다

마지막으로 count를 출력하면 된다.

 

코드

N = int(input())

node = list(map(int, input().split()))

delete = int(input())

count = 0

def DFS(num, arr):
    arr[num] = -2
    for i in range(len(arr)):
        if num == arr[i]:
            DFS(i, arr)

DFS(delete, node)

for i in range(len(node)):
    if node[i] != -2 and i not in node:
        count += 1

print(count)