이번 문제는 깊이우선탐색을 통해 해결하였다. 인접 리스트 형태로 트리를 저장하였다. 이때 각 노드의 리스트에 저장되는 내용은 자신의 자식 노드들이 된다. 그리고 dfs()함수를 루트부터 시작하여 현재 노드가 제거할 노드라면 함수를 종료하고, 현재 노드의 자식이 없을 경우에는 카운팅 변수를 증가시킨 후 함수를 종료하고, 그 외에는 현재 노드의 자식 노드로 재귀호출을 진행한다. 처음 작성 시에 놓친 부분은 만약에 노드를 제거했을 때, 그 노드의 부모 노드가 리프 노드가 될 경우에도 리프 노드로 카운팅을 해야한다는 사실이었다. 그래서 노드의 자식을 순회할 때 자식이 1개이고, 다음 자식이 제거해야할 노드인 경우에는 카운팅 변수를 증가시키고 함수를 종료시켰다. 그리고 최종적으로 구해진 카운팅 변수를 출력하는 방식으로 구현하였다.

• dfs함수를 cur을 인자로 갖도록 선언한다.
  -> cnt를 global로 선언하여 함수 내에서 사용할 수 있도록 한다.
  -> 만약 cur이 r과 같다면 함수를 종료시킨다.
  -> 만약 tree[cur]이 비어있을 경우(리프노드일 경우),
  --> cnt를 1 증가시킨다.
  --> 함수를 종료시킨다.
  -> tree[cur]을 순회하는 n에 대한 for문을 돌린다.
  --> 만약 n이 r이고 tree[cur]의 길이가 1일 경우,
  ---> cnt를 1 증가시킨다.
  ---> 함수를 종료시킨다.
  --> dfs(n)을 재귀호출한다.
• n을 입력받는다.
• tmp에 각 노드의 부모 노드를 입력받는다.
• 제거할 노드 r을 입력받는다.
• 각 노드의 자식 노드를 저장할 리스트 tree를 2차원 리스트로 선언한다.
• 루트 노드를 저장할 변수 root를 0으로 선언한다.
• 카운팅 변수 cnt를 0으로 선언한다.
• tmp의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> 만약 tmp[i]가 -1일 경우,
  --> root를 i로 갱신한다.
  -> 그 외에는 tree[tmp[i]]에 i를 넣는다. (자식 노드를 저장)
• dfs(root)를 호출한다.
• cnt를 출력한다.

Code

def dfs(cur):
    global cnt
    if cur==r:
        return
    if not tree[cur]:
        cnt+=1
        return
    for n in tree[cur]:
        if n==r and len(tree[cur])==1:
            cnt+=1
            return
        dfs(n)
n=int(input())
tmp=list(map(int, input().split()))
r=int(input())
tree=[[] for _ in range(n)]
root=0
cnt=0
for i in range(len(tmp)):
    if tmp[i]==-1:
        root=i
    else:
        tree[tmp[i]].append(i)
dfs(root)
print(cnt)