[백준] 1068번 : 트리

문제

 

 

접근 방식

트리를 순회하면서 해당 노드에 자식이 없다면

해당 노드는 리프 노드라는 것을 알 수 있으니

카운트를 1씩 증가시켜주면 된다.

 

처음에는 루트 노드가 무조건 0번인줄 알고 풀었는데 틀려서

찾아 보니 루트 노드는 랜덤이기 때문에 이 부분만 조심해서

입력으로 -1을 받을 때 해당 부분을 루트 노드로 지정하고 탐색해주면 된다.

 

또한 이진 트리가 아닌 일반적인 트리이기 때문에

자식이 꼭 최대 두 개가 아니라 이상일 수도 있다.

 

 

풀이

public class Main {

	private static int remove, leaf = 0;
	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();

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

		int root = 0;
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		remove = Integer.parseInt(br.readLine());

		for (int i = 0; i < n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 0; i < n; i++) {
			int p = Integer.parseInt(st.nextToken());
			if (p == -1) {
				root = i;
				continue;
			}
			near.get(p).add(i);
		}

		if (remove == root) {
			System.out.println(0);
			return;
		}

		dfs(root);

		System.out.println(leaf);
	}

	private static void dfs(int cur) {
		int size = near.get(cur).size();

		for (int next : near.get(cur)) {
			if (next == remove) {
				size--;
				continue;
			}
			dfs(next);
		}

		if (size == 0) leaf++;
	}
}