[Java] BOJ1068_트리

www.acmicpc.net/problem/1068

1068번: 트리

---

트리에서 어떤 노드를 지웠을 때 남아있는 리프 노드의 수를 출력하는 문제이다.

해당 노드를 지우고 트리를 탐색해 리프 노드의 수만 세어주면 된다.

트리구조를 만들 때 리스트를 사용해서 만들었기 때문에 remove 함수로 해당 노드를 지우고 dfs방식으로 트리를 탐색해 리프 노드의 수를 셌다.

리프 노드는 자식 노드가 없는 노드로, 리스트 크기가 0인 노드를 의미한다.

 

*예제는 각 노드의 부모 번호가 오름차순으로 들어오지만 실제로는 그렇지 않다. 따라서 첫 번째 노드가 루트 노드가 아닐 수도 있음을 주의해야 한다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static Node[] tree;
	static int res = 0;
	static boolean[] visit;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		tree = new Node[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			tree[i] = new Node(i);
		}
		int[] temp = new int[N];
		int root = 0;
		for (int i = 0; i < N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			temp[i] = parent;
			if(parent == -1) {
				root=i;
				continue;
			}
			tree[parent].list.add(i);
		}
		int del = Integer.parseInt(br.readLine());
		if(temp[del] == -1) {
			System.out.println(0);
			return;
		}
		visit = new boolean[N];
		//타겟 노드 삭제
		tree[temp[del]].list.remove((Object) del);
		
		dfs(root);
		System.out.println(res);
	}
	
	private static void dfs(int cur) {
		int size = tree[cur].list.size();
		if(size == 0) {
			res++;
			return;
		}
		
		visit[cur] = true;
		for (int i = 0; i < size; i++) {
			int node = tree[cur].list.get(i);
			if(!visit[node]) {
				dfs(node);
			}
		}
	}

	public static class Node{
		int num;
		ArrayList<Integer> list = new ArrayList<>();
		protected Node(int num) {
			super();
			this.num = num;
		}
	}
}