문제 이해

트리가 주어진다.
이 때 한 개의 노드를 지울 경우, 남아 있는 트리 중 리프 노드의 개수를 구하는 문제이다.

---

문제 풀이

먼저 Root Node를 찾는 것이 우선시 될 것이다.
Root Node는 부모 노드가 존재하지 않는 Node이므로, -1이 주어진 노드가 루트 노드가 될 것이다.

A Node의 경우, Tree 성질에 따라 parent Node를 단 한개만 가지고 있다.
따라서, Node의 관계를 저장할 때, list[부모 Node]의 원소는 자식 Node의 Number를 가지도록 저장했다.
(ex) list[0] = {1,2,3}일 경우, 0의 자식은 1,2,3번 Node

이후 bfs나 dfs를 통해 Tree를 순회할 수 있을 것이다.

이번 풀이 같은 경우, 두 방법 모두 가능한 방법이지만 조금 더 알고리즘 구현에 대한 파악이 쉬운 BFS를 통해 풀기로 했다(재귀함수는 한 눈에 알아보기는 조금 힘들다)

해당 Node가 Leaf Node인 경우는 2가지일 것이다.

1. 자식 Node가 아무것도 저장되어 있지 않은 Node

2. 자식 Node가 하나만 존재하는데, 그 Node가 삭제시킬 Node일 경우

위 2가지 경우를 찾아 총 Leaf Node의 수를 찾을 수 있다.

또한, BFS를 실행하는 도중 삭제해야할 Node를 만난다면 Queue에 포함시키지 않을 것이다.
문제에서 해당 Node를 삭제하면 해당 Node를 Root로 하는 Subtree도 모두 삭제된다고 하였다. 따라서 삭제시킬 Node를 아예 방문하지 않음으로써 해당 Node를 Root로 가지는 Subtree에 대한 방문을 막았다.

• Root Node를 삭제시킬 경우 Tree의 모든 Node가 삭제되는 것이므로 무조건 0을 출력하도록 했다.

---

코드

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

public class Main {
	
	static int N;
	static ArrayList<Integer>[] nodes;
	
	static void find_leaf(int root, int erase) {
		Queue<Integer> queue = new LinkedList<>();
	
		if(erase==root) {
			System.out.println(0);
			return;
		}
		queue.add(root);
		
		int leaf = 0;
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			
			if(nodes[tmp].isEmpty()) { 
            // 자식 노드가 아예 없는 경우 : Leaf Node
				leaf++;
				continue;
			}
			
			if(nodes[tmp].size()==1 && nodes[tmp].get(0)==erase) {
                // 자식 Node가 하나 존재하지만, 자식 Node가 삭제할 Node이므로 
                // 결국 Leaf Node가 될 것임
				leaf++;
				continue;
			}
			
			
			for(int s:nodes[tmp]) {
                // 지울 Node를 Root로 하는 Subtree를 방문하지 않도록 
                // 지울 Node에 대한 접근을 막아줌
				if(s!=erase) queue.add(s);
			}
		}
		
		System.out.println(leaf);
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		nodes = new ArrayList[N];
		
		for(int i =0;i<N;i++) nodes[i] = new ArrayList<>();
		
		int root = 0;
		for(int i =0;i<N;i++) {
			int tmp = sc.nextInt();
			if(tmp==-1) root  = i; // 부모 노드를 찾음
			else {
				nodes[tmp].add(i); // i의 부모는 tmp Node
			}
		}

		int erase = sc.nextInt();
		
		find_leaf(root, erase);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3번째 줄 틀렸습니다 : Root를 지울 Node로 선정할 경우에 대한 처리를 해주지 않아 틀렸다.