[Backjoon] 1068 트리 Python 문제 풀이

출처 : 트리

문제해석

1. 제거하고자 하는 입력값을 dfs 함수에 넘겨준다.
2. 넘겨준 입력값을 인덱스로 하는 배열값을 제거한다는 의미로 -2로 변경한다.(-1은 루트 노드이므로)
3. 제거한 인덱스를 부모노드로 가지고 있는 노드를 찾아 제거하기 위해 dfs함수를 재귀 호출한다.
4. 재귀가 종료되고 삭제될 노드들은 전부 -2를 배열값으로 지니고 있다.
5. -2가 아니면서, 다른 노드의 부모노드도 아닌 원소(초기 배열 초기화 단계에서 포함되지 않은)를 찾을 때마다 ans를 1씩 늘린다.

해답코드

#트리
import sys
input = sys.stdin.readline

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

ans=0

def dfs(num):
    vList[num] = -2
    for i in range(n):
        if num == vList[i]:
            dfs(i)

dfs(delete)

for i in range(n):
    if vList[i] != -2 and i not in vList:
        ans += 1

print(ans)