백준 - 1068번 트리 - java

https://www.acmicpc.net/submit/1068/35162027

접근법

1. 기본적인 트리를 생성하고 했으나 그럴필요는 없어보임
2. Node배열을 N개만큼 생성해서 각 인덱스에 ArrayList를 주고, 각각 자식을 add하여 tree배열을 완성함
3. 만약 제거하는 인덱스가 루트노드면 바로 0출력 후 종료
4. 아니면, q에 root노드를 넣는걸로 시작.
   3-1. q에 있는 노드의 자식들을 bfs로 탐색
   3-2. 자식의 인덱스가 만약 제거하고자 하는 인덱스면 무시, 그렇지 않으면 q에 넣기
   3-3. 현재 q에 있던 인덱스에서 자식이 없거나, 있어도 제거되는 자식이면 리프노드이므로 카운트 올림

소스

import java.util.*;
import java.io.*;
public class Main {
	static int N;
	static Node[] tree;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		tree = new Node[N];
		for(int i = 0; i < N; i++) tree[i] = new Node(i);
		
		Node rootNode = null;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			if(parent == -1) rootNode = tree[i];
			else tree[parent].child.add(i); //부모의 list에 현재 index를 넣기
		}
		
		st = new StringTokenizer(br.readLine());
		int deleteIdx = Integer.parseInt(st.nextToken());
		if(deleteIdx == rootNode.index) {
			System.out.println(0);
			return;
		}
		int count = 0;
		
		Queue<Node> q = new LinkedList<Node>();
		q.offer(rootNode);
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			boolean isLeaf = true;
			
			for(int i = 0; i < cur.child.size(); i++) {
				if(cur.child.get(i) == deleteIdx) continue;
				q.offer(tree[cur.child.get(i)]);
				isLeaf = false;
			}
			
			if(isLeaf) count++;
		}
		
		System.out.println(count);
	}

}

class Node{
	int index;
	ArrayList<Integer> child;
	
	Node(int index){
		this.index = index;
		child = new ArrayList<Integer>();
	}	
}