🔗 Problem

https://www.acmicpc.net/problem/1068

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 트리

public class BJ1068 {
	
	static int n;
	static int root;
	static int del;
	static int[] leaf;		// 각 노드 기준 subtree의 leaf 수 저장
	static ArrayList<Integer>[] list;	// 인접 노드 저장
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		leaf = new int[n];
		list = new ArrayList[n];
		
		for(int i = 0; i < n; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			int x = Integer.parseInt(st.nextToken());
			
			if(x == -1) root = i;
			else list[x].add(i);
		}
		
		del = Integer.parseInt(br.readLine());
        
		int result = findLeaves(root) - findLeaves(del);
		int delParent = findDelParent(del);
		if((list[delParent].size() -1) == 0) result++;		// del을 삭제하면 del의 부모가 leaf node가 되는 경우
		
		System.out.println(result);
		
	}
	
	private static int findDelParent(int del) {
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < list[i].size(); j++) {
				if(del == list[i].get(j)) return i;
			}
		}
		
		return root;
	}
	
	private static int findLeaves(int x) {			// x를 기준으로 subtree의 leaf 수를 반환
		
		int cnt = 0;	
		if(list[x].size() == 0) return 1;			// 인접 노드가 없으므로 x 자신이 leaf인 경우 
		for(int i = 0; i < list[x].size(); i++) {
			cnt += findLeaves(list[x].get(i));		// x의 인접 노드들에 대해 findLeaves() 실행
		}
		
		return leaf[x] = cnt;						
	}
	
}

👩‍💻 Code - DFS

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 트리

public class BJ1068_2 {
	
	static int n;
	static int root;
	static int del;
	static boolean[] visited;		
	static ArrayList<Integer>[] list;
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		visited = new boolean[n];
		list = new ArrayList[n];
		
		for(int i = 0; i < n; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			int x = Integer.parseInt(st.nextToken());
			
			if(x == -1) root = i;
			else list[x].add(i);
		}
		
		del = Integer.parseInt(br.readLine());
		visited[del] = true;
		
		System.out.println(dfs(root));
		
	}
	
	private static int dfs(int x) {
		
		// 방문했던 경우
		if(visited[x]) return 0;
		
		visited[x] = true;
		// leaf인 경우
		if(list[x].size() == 0 || (list[x].size() == 1 && list[x].get(0) == del)) return 1;		// del인 경우도 leaf로 여겨서 탐색하지 않도록. 즉 del 이하 subtree를 삭제한 것과 같은 효과
		
		// non-leaf인 경우
		int cnt = 0;
		for(int i = 0; i < list[x].size(); i++) {		// x의 각 leaf에 대해
 			cnt += dfs(list[x].get(i));
		}
		return cnt;
	}
	
	
}

📌 Note

아이디어

• 풀고 나니 DFS로 구현했다는 걸 알았다.
• 전체 tree의 leaves 수 - deleted node 기준 subtree의 leaves 수를 구한 뒤, deleted node를 삭제할 경우 그 부모가 leaf가 된다면 +1 하여 답을 구했다.
• delParent를 찾아야 해서 깔끔한 풀이는 아닌 것 같다.
• Better solution 찾아보기

다른 soluton(DFS 정석)으로도 풀어봤는데 효율성 면에선 비슷하다.