백준 -1068번 트리

문딤·2022년 7월 26일

트리

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

문제 방향성
1. delete , leaf노드 메소드 구현
2. 자식노드가 없는 노드를 어떻게 찾을것인가

소스코드

풀이 방법

Delete , Leaf find


static List<Integer>[] list;
    static void removeNode(int node){
        if(list[node].size()>0){
            int size = list[node].size();
            while(size > 0){
                int child = list[node].get(--size);
                removeNode(child);
            }
        }
        for (int i = 0; i < n; i++) {
        if(list[i].contains(node)){
            for (int j = 0; j < list[i].size(); j++) {
                if(list[i].get(j) == node){
                    list[i].remove(j);
                }
            }
        }
        }

    }
    static int findleaf(int node){
        Queue qu = new LinkedList();
        qu.add(node);
        int cnt =0;

        while(!qu.isEmpty()){
            int pos = (int) qu.poll();
            if(list[pos].size() == 0){
                cnt++;
                continue;
            }
            for (int next: list[pos]
                 ) {
                qu.add(next);
            }
        }
        return cnt;
    }

Main

  static StringBuilder sb =new StringBuilder();
    static boolean[] check;
    static int [][] arr;
    static int n;

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

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

            n = Integer.parseInt(br.readLine());
            list = new ArrayList[n];

                for (int i = 0; i < n; i++) {

                    list[i]= new ArrayList<>();
                }
                //LIST에 더해주기

                st= new StringTokenizer(br.readLine()," ");
                int root= -1;
                for (int i = 0; i <n ; i++) {
                    int num =Integer.parseInt(st.nextToken());
                    // -1은 루트노드니깐 값넣고 continue
                    if(num ==-1){
                        root =i;
                        continue;
                    }else{
                        //root index저장
                        list[num].add(i);
                    }

                }

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

                removeNode(K);

                if(K == root){
                    System.out.println(0);
                }else{
                    System.out.println(findleaf(root));
                }
}
}