[BOJ 1068] 트리

1. 트리의 형태가 무조건 이진 트리라는 조건은 없다

2. 트리의 루트가 무조건 0번 노드라는 조건은 없다

 

위의 두 조건을 염두하여 풀어야 할 문제

 

- 부모노드를 저장할 배열 parent

- 나의 자식노드를 저장할 List[] Childs

 

- 삭제해야할 노드의 부모노드(parent[num]) 로 가서

  부모노드에서 삭제해야할 노드를 자식목록에서 지운 후 bfs를 탐색한다. == child[parent[num]] 안에 있다.

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;


public class Main {

	static StringBuilder sb = new StringBuilder();
	static int ans;
	static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));

		N= Integer.parseInt(br.readLine());

		int num;
		List<Integer> childs[]= new ArrayList[N+1]; // 인접 리스트 구현 위한 2차원 리스트
		int[] parent = new int[N + 1];
		for (int i=0; i<N; i++) {
			childs[i] = new ArrayList<>();
		}
		
		String[] input = br.readLine().split(" ");
		
		int root = 0;
		for (int i=0; i<N; i++) {
			num = Integer.parseInt(input[i]);

			if (num == -1) { // root노드의 등장
				root = i;
				continue;
			}
			parent[i] = num; // i의 부모는 num이다.
			childs[num].add(i); // num의 자식은 i이다.
			
		}
		
		num = Integer.parseInt(br.readLine());
		
		if (num == root) {
			System.out.println(0);
			return;
		}
		
		//System.out.println(parent[num]);
		for (int i=0; i<childs[parent[num]].size(); i++) {
			
			if (childs[parent[num]].get(i) == num) {
				childs[parent[num]].remove(i);
				break;
			}
		}
		
		ans = bfs(childs,num,root);	

		System.out.println(ans);
		
		
	}
	private static int bfs(List<Integer>[] childs, int delete,int root) {
		
		 int cnt = 0;
		 
		 Queue<Integer> q = new ArrayDeque<>();
		 
		 q.add(root); //  root 노드로부터 시작.
		 
		 int temp;
		 while (!q.isEmpty()) {
			 
			 temp = q.poll();
			 
			 if (childs[temp].size() == 0) {
				 cnt++;
				 continue;
			 }
			 
			 for (int i=0; i < childs[temp].size(); i++) {
				 
				 q.add(childs[temp].get(i));
			 }
			 
		 }
		 
		 return cnt;
	}

}