문제

풀이

• 루트 노드에서 깊이 탐색 시작해서 지울 노드는 탐색 진행 X

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n=Integer.parseInt(br.readLine());
        ArrayList<Integer>[] adj=new ArrayList[n];
        for(int i=0;i<n;i++)adj[i]=new ArrayList<>();
        st=new StringTokenizer(br.readLine());
        int root=-1;
        for(int i=0;i<n;i++){
            int parent=Integer.parseInt(st.nextToken());
            if(parent==-1){
                root=i;
                continue;
            }
            adj[parent].add(i);
        }
        int del=Integer.parseInt(br.readLine());
        cnt=0;
        if(root!=del)dfs(adj,root,del);
        System.out.println(cnt);
    }

    static int cnt;

    static void dfs(ArrayList<Integer>[] adj,int x,int del){
        if(adj[x].isEmpty()){
            cnt++;
            return;
        }
        for(int next:adj[x]){
            if(next==del){
                if(adj[x].size()==1)cnt++;
                continue;
            }
            dfs(adj,next,del);
        }
    }
}

#트리#dfs