[G5] 트리 : Java : 1068 - BFS

문제

1068번: 트리

 

---

 

어떻게 풀것인가?

트리 형태를 만든 다음 삭제 노드를 부모 노드와 끊어준다.  노드의 부모는 무조건 1개이기 때문에, 끊어주면 탐색을 할 수 없다.

트리를 DFS 탐색으로 탐색을 진행한다. BFS나 DFS 둘다 되겠지만 구현이 쉬운 BFS를 선택했다.

 

 

 

문제 알고리즘

1. parent 배열에  각 노드의 parent 값을 저장한다.
2. parent  배열 이용하여 삭제할 노드를 부모 노드에서 제거 한다.
3. BFS 탐색을 진행하면서 leaf 노드를 찾는다.

 

주의할 점

 루트를 제거할 수도 있다는 것을 놓치면 안된다. 이 문제는 친절하게도 예제로 주어져 있어 캐치할 수 있었지만, 주어지지 않았다면 놓쳤을 것이다. 이때는 바로 0을 출력하고 종료한다.

 

 

 

전체 코드 - Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    static int [] parnet;
    static List<Integer> [] tree;
    static int root = 0;
    static Boolean []  visited;
    static int result = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        parnet = new int[n+1];
        tree = new ArrayList[n+1];
        visited = new Boolean[n+1];
        Arrays.fill(visited, false);

        for(int i=0; i<n; i++){
            tree[i] = new ArrayList<Integer>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int i = -1;
        while(st.hasMoreTokens()){
            i++;
            int parentValue = Integer.parseInt(st.nextToken());
            parnet[i] = parentValue;
            if(parentValue != -1){
                tree[parentValue].add(i);
            }
        }

        int deleteNode = Integer.parseInt(br.readLine());
        int deleteNodeParent = parnet[deleteNode];

        // 루트를 제거할 시
        if(deleteNodeParent == -1 ){
            System.out.println(0);
        }

        else{
            int idx = 0;
            for(int value :tree[deleteNodeParent] ){
                if(value == deleteNode){
                    tree[deleteNodeParent].remove(idx);
                    break;
                }
                idx++;
            }

            // 루트 찾기
            idx = 0;
            for(int p : parnet){
                if(p == -1){
                    root = idx;
                    break;
                }
                idx++;
            }

            // 트리 탐색
            visited[root] = true;
            findLeafNodeCount(root);
            System.out.println(result);
        }

    }

   static void findLeafNodeCount(int root){
        // bfs
       if(tree[root].size() == 0){
           result++;
           return;
       }
       Iterator<Integer> iterator = tree[root].iterator();

       while(iterator.hasNext()){
           int v = iterator.next();
           if(!visited[v]){
               visited[v] = true;
               findLeafNodeCount(v);
           }

       }
   }

}