[백준] 1068 트리 - Java

 

 

 

리스트를 사용해 트리를 구현하고, 지울 요소를 입력받은 후 해당하는 요소를 리스트에서 모두 제거해 준 다음 dfs 돌려서 리프 노드의 수를 탐색해줬다.

 

 

리스트에서 indexOf(i) 메서드를 통해 위치를 리스트에 포함된 i의 위치를 얻고, 얻은 위치를 바탕으로 요소를 제거할 수 있었다.. 

 

트리를 여러 개의 subtree로 분할한 후 각각의 subtree에 대해 또 subtree로 분할하고.. 이 작업을 자식이 없는 노드가 될 떄 까지 반복한 후 개수를 갱신해 주는 방식으로 풀어도 괜찮을 것 같다. (재귀 느낌으로?)

 

 

 

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

public class Main {

	static int N;	
	static ArrayList<Integer>[] list;	
	static int root;
	static int delete;

	static int cnt;

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

			N = Integer.parseInt(br.readLine());
			list = new ArrayList[N];			
			
			for(int i=0; i<N; i++){
				list[i] = new ArrayList<>();
			}

			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int i=0; i<N; i++){
				int tmp = Integer.parseInt(st.nextToken());
				if(tmp == -1){
					root = i;
					continue;
				}
				list[tmp].add(i);
			}
			delete = Integer.parseInt(br.readLine());			

			for(int i =0; i<N; i++){
				if(list[i].contains(delete)){
					list[i].remove(list[i].indexOf(delete));
				}
			}

			if(root != delete){
				dfs(root, -1);
				System.out.println(cnt);
			}else{
				System.out.println(0);
			}
				
	}


	static void dfs(int x, int parent){
		if(list[x].isEmpty()){
			cnt++;
		}
		for(int y: list[x]){
			if(y == parent){
				continue;
			}
			dfs(y,x);			
		}
	}
}