[PS] BOJ1068 트리 ( tree ) with JAVA

1068번: 트리

 

 

◎ 문제풀이 

 

특정 노드를 삭제하면 자식 노드들도 삭제가 될 때, 리프노드의 개수를 구하는 문제이다. 풀이는 3단계로 이루어 진다.

 

Step1) 트리를 그래프의 인접리스트 구조로 구현

각 노드의 자식노드를 List에 저장한다. 그래프의 인접리스트 방식으로 트리를 구현하는 것이다.

 

Step2) DFS 탐색으로 노드 삭제

특정 노드를 삭제하면 자식노드와 자식의 자식노드도 삭제해야 한다. DFS탐색으로 자식의 자식까지 삭제하고 삭제 여부를 테이블 자료구조에 저장한다.

 

Step3) 리프노드 개수 카운트 

리프노드는 인접리스트 사이즈가 0인 노드가 리프노드이다. 그런데 삭제된 노드가 인접리스트에 저장되어 있을 수 있다. 그러므로 각 노드의 인접리스트를 검사하며 삭제 테이블이 true인지 확인한다. 

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

//BOJ1068 트리
public class Main {

    static List<Integer>[] tree;
    static boolean[] deleted;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        tree = new List[n];
        deleted = new boolean[n];

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        // Step1) 트리 구성하기
        for(int i=0;i<n;i++){
            int parent = Integer.parseInt(st.nextToken());
            if(parent != -1) tree[parent].add(i);
        }

        // Step2) 노드 삭제 
        int deleteNode = Integer.parseInt(br.readLine());
        deleteTree(deleteNode);

        // Step3) 리프노드 카운트
        int leafNodeCount = 0;
        for(int i=0;i<n;i++){
            if(deleted[i]) continue;
            if(isLeafNode(i)) leafNodeCount++;
        }

        //출력
        System.out.println(leafNodeCount);


    }

    public static void deleteTree(int node){
        if(deleted[node]) return;

        deleted[node] = true;
        for (Integer child : tree[node]) {
            deleteTree(child);
        }
    }

    public static boolean isLeafNode(int node) {
        for (Integer child : tree[node]) {
            if (deleted[child] == false) return false;
        }
        return true;
    }

}