[BOJ 1068] 트리(Java, 간단한 풀이, Set)

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

1068번: 트리

 

1. 입력을 처리할 때, 각 노드의 부모 노드를 기억, 노드의 자식 노드들을 기억할 수 있도록 데이터를 저장하는 자료구조를 사용한다.

 

 

 

2. 제거해야하는 노드가 있으면, 부모 노드의 자식 노드에서 해당 노드를 지우고, 제거해야하는 노드와 연결된 노드들을 큐를 사용해 모두 체크한다.

 

 

 

3. 전체 노드들을 탐색하면서, 자식 노드가 0이며 제거햐아하는 노드와 연결되지 않은 것을 정답의 값에 추가한다.

 

---

 

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.valueOf(br.readLine());
        String[] sArr = br.readLine().split(" ");
        int K = Integer.valueOf(br.readLine());
        
        boolean[] removeChk = new boolean[N];
        Arrays.fill(removeChk, false);
        int[] pArr = new int[N];
        ArrayList<HashSet<Integer>> cList = new ArrayList<>();
        
        for(int i = 0; i < sArr.length; i++)
            cList.add(new HashSet<Integer>());
        
        for(int i = 0; i < sArr.length; i++){
            int parent = Integer.valueOf(sArr[i]);
            pArr[i] = parent;    
            
            if(parent != -1)
                cList.get(parent).add(i);
        }
        
        int parent = pArr[K];
        if(parent == -1){
            bw.write("0" + "\n");
            bw.flush();
            return;
        }
        
        cList.get(parent).remove(K);
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(K);
        removeChk[K] = true;
        
        while(!q.isEmpty()){
            for(int i : cList.get(q.poll())){
                q.offer(i);
                removeChk[i] = true;
            }
        }
        
        int answer = 0;
        int idx = 0;
        for(HashSet<Integer> hs : cList){
            if(hs.size() == 0 && !removeChk[idx])
                answer += 1;
            idx += 1;
        }
        
        bw.write(answer + "\n");
        bw.flush();
    }
}