1068 트리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {	
	
		static boolean visit[];
		static ArrayList<Integer> [] tree;
		static int result;
	
	public static void main(String[] args) throws IOException{	
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine(), " " );
		int N = Integer.parseInt(st.nextToken());
		tree = new ArrayList[N+1];
		visit= new boolean[N+1];
		result = 0;
	
		for(int i=0; i<N; i++) {
			tree[i]= new ArrayList<>();
		}
		
		 st= new StringTokenizer(br.readLine(), " " );
		 int root = 0;
		 for(int i=0; i<N; i++) {
			 
			 int value = Integer.parseInt(st.nextToken());		 
			 
			 if(value == -1) {				 
				 root = i;
				 
			 }else {
				 
				 tree[i].add(value);
				 tree[value].add(i);
				 
			 }			 
		 }		
		 
		 st= new StringTokenizer(br.readLine(), " " );
		 int M = Integer.parseInt(st.nextToken());	
		 
		 // 삭제할 노드는 visit -> true 해서 dfs 탐색하지 않도록.
		 visit[M] = true;
		 
		 // 삭제할 노드가 root 노드와 같다면, 결과 -> 0 출력함.
		 if(M!=root) {
			 solve(root);
		 }		 
		 System.out.println(result);
		
	}
	
	
	public static void solve(int node) {
		
		visit[node]  = true;		
		int size = tree[node].size();		
		int count = 0;
		
		for(int i=0; i<size; i++) {
			
			int number = tree[node].get(i);
			
			if(!visit[number]) {
				
				visit[number]= true;
				solve(number);			
				count++;
			}			
		}
		
        // 자식 노드가 없으므로
		if(count == 0 ) {
			result++;
		}
	}
}

 

참고 블로그 : https://usedto-wonderwhy.tistory.com/175

[백준 1068] 트리 (JAVA)