[백준] 1068번:트리 (Python 파이썬)

문제

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

1068번: 트리

 

풀이 및 소스코드

dfs로 풀어주었다.

여기서 중요한 점이 삭제할 노드의 부모노드가 가진 자식노드가 삭제할 노드 밖에 없을 때다.

노드를 삭제하면 부모노드가 리프가 되므로 +1을 해줘야 하기 때문.

아래 그림을 보면 쉽게 이해할 수 있다.

 

이러한 케이스에서 올바른 출력을 하기 위해서,

dfs가 끝난 후 만약 삭제할 노드의 부모노드가 가진 자식노드의 개수가 하나 뿐이라면

ans에 +1을 해주었다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(x):
    global ans
    if (x not in arr and x != del_node):
        ans+=1
        return
    else:
        for i in range(n):
            if(arr[i]==x and i!=del_node):
                dfs(i)
    return ans

n = int(input())
arr = list(map(int, input().split()))
del_node = int(input())
start = arr.index(-1)
ans = 0
if(start == del_node):
    print(ans)

else:
    dfs(start)
    if (arr.count(arr[del_node])==1):
        ans+=1
    print(ans)