💚트리

 

 

1. 문제 설명

1068번: 트리

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

www.acmicpc.net

트리에서 A번 노드를 없앴을 때 리프 노드의 개수를 구하여라

2.푸는 원리

위의 설명 처럼, 나는 제거되는 중간 노드가 가진 leaf 노드에 -111 이란 가상의 노드를 새로 더해주었고, 그렇게 해서 leaf 노드가 아닌 것으로 만들었다. 그리고 다시 전체 노드에서 자식 노드가 없는 노드의 개수를 세어줘서 리프 노드의 개수를 구했다. 하지만 이 알고리즘에서 예외가 되는 지점이 존재했다. 만약 위의 예시의 노드 2처럼 자신이 가진 모든 leaf 노드가 -111이란 가상의 노드를 가진다면, 실질적으로 2가 가진 모든 자식 노드가 제거 되었다는 소리임으로 2가 leaf 노드가 된다. 따라서 나는 만약 어떤 노드 A가 내가 지워야 하는 노드만 자식으로 가진다면, 해당 노드를 leaf 노드로 만드는 예외처리 가정 또한 거쳤다.

3. 코드 분석

Copy

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

public class Main{

    static int N;
    static ArrayList<Integer> [] lists;


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

        lists = new ArrayList[N];

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

        // ArrayList를 이용해, 트리 구현
        // index가 자식노드, 값이 부모 노드
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if(parent == -1){
                continue;
            }
            lists[parent].add(i);
        }


        // 자식이 있는 원소는 모두 특정 수들로 ArrayList<Integer>가 하나라도 찼을 것이다.
        // 반면 자식이 없는 리프노드는 empty이다.

        // 특정 노드 삭제 시에는 해당 노드의 리프 노드까지 가서 해당 노드에 -1을 넣어준다.
        int deleteNode = Integer.parseInt(br.readLine());

        ArrayDeque<Integer> aq1 = new ArrayDeque<>();

        aq1.add(deleteNode);

        while(!aq1.isEmpty()){
            int Qsize = aq1.size();

            for (int i = 0; i < Qsize; i++) {
                int nowNode = aq1.poll();

                if(lists[nowNode].isEmpty()){
                    lists[nowNode].add(-111);
                }
                else{
                    for (int j = 0; j < lists[nowNode].size(); j++) {
                        aq1.add(lists[nowNode].get(j));
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if(lists[i].contains(deleteNode) && lists[i].size() > 1){
                break;
            }
            if(lists[i].contains(deleteNode) && lists[i].size() == 1){
                lists[i].clear();
            }
        }


        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if(lists[i].isEmpty()) cnt++;
        }

        System.out.println(cnt);
    }
}