[백준] 1068 트리 - JAVA

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

1068번: 트리

 

 

[풀이]

• DFS 탐색 
• 인접리스트에 각 노드의 자식 노드(들) 저장, 1차원 정수배열에 각 노드의 부모 노드를 저장한다. 
• 지워질 노드(erase)가 주어지면, 
  1. erase의 자식 노드를 모두 삭제한다. (erase 리스트를 비운다.) 
  2. erase의 부모 노드 리스트에서 erase를 삭제한다. 
• 만약 지운 노드가 루트노드라면 0 출력 후 종료. 
• 그렇지 않다면 루트노드에서 시작하여 DFS 탐색을 시작한다. 탐색 중 노드의 자식 갯수가 0개라면 리프노드 ++ 

---

 

[구현 과정]

• List<ArrayList<Integer>> child : 각 노드의 자식 노드(들)을 리스트로 저장 
• int[] parent : 각 노드의 부모 노드 저장 
• int erase : 지울 노드 
• int root : 루트 노드 
• int cnt : 리프 노드의 갯수 

 

1. 주어진 입력값에 따라 parent 배열에 각 노드의 부모 노드를 저장하고 child 리스트에 각 노드의 자식 노드들을 저장한다. (부모가 -1이라면 해당 노드는 root 노드이다.)

 

2. 지울 노드 erase를 입력받고, 만약 erase 가 -1이라면 루트노드를 지우는 것이므로 0 출력 후 종료 한다. 

 

3. 그렇지 않다면 erase 의 부모노드에서 erase를 찾아(indexOf(erase)) 지우고, erase의 자식 노드를 모두 삭제한다.  

💡erase의 부모노드 : parent[erase] 
💡erase의 부모노드의 자식노드(들) 리스트 : child.get(parent[erase]) 
💡erase의 자식 노드(들) 리스트 : child.get(erase) 

 

 

4. root 노드에서 DFS 탐색을 시작하여, 만약 탐색하는 노드의 자식 노드 갯수가 0일 경우 cnt ++ 

 

5. DFS 탐색 종료 후, cnt 을 출력. 

 

---

 

[소스 코드]

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

public class Main {
	static List<ArrayList<Integer>> child = new ArrayList<>(); // 자식 노드 저장 
	static int root; //루트 노드 
	static int erase;
	static int cnt=0;
	static int parent[]; 
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		int N= Integer.parseInt(br.readLine()); //노드의 갯수 
		for(int i=0; i<N; i++) child.add(new ArrayList<>()); 
		parent = new int [N]; 
		
		st= new StringTokenizer(br.readLine()); 
		for(int i=0; i<N; i++) {
			int p = Integer.parseInt(st.nextToken()); //현재 i노드의 부모 
			parent[i] = p; 
			if(p == -1) {
				root = i; //루트노드 
				continue;
			}
			child.get(p).add(i); 
		}
		
		erase= Integer.parseInt(br.readLine()); //지울 노드 
		if(parent[erase] == -1) {
			System.out.println(0);
			return; 
		}
		child.get(parent[erase]).remove(child.get(parent[erase]).indexOf(erase)); 
		child.get(erase).clear(); 
		
		dfs(root);
		System.out.println(cnt);
	}//end of main
	
	private static void dfs(int node) {
		if(child.get(node).size() == 0) {
			cnt++;
			return; 
		}
		else {
			for(int next: child.get(node)) {
				dfs(next);		
			}
		}
	}
}//end of class