[BOJ][Java] 1068번 트리

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1068

 

문제 자체는 리프노드의 개수를 세는 문제로 단순하다.

하지만 단순 리프노드를 세는 게 아닌 중간에 노드를 삭제했을 때 리프노드의 개수를 구해야 한다.

 

문제를 2가지 방법을 해결해봤다.

첫 번째 방법

첫 번째는 자식노드의 개수를 직접 카운팅 하여 자식노드가 없는 노드의 개수를 세는 방식이다.

먼저 노드를 삭제하기 이전의 자식노드 개수로 counts배열을 초기화한다.

이후 만약 2번 노드를 삭제한다면 2번 노드의 부모노드인 0번 노드의 자식개수를 1개 빼준다.

그다음 2번 노드와 2번 노드의 자식들은 자식노드의 개수를 -1로 바꿔준다.

 

package boj;

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

public class BOJ1068_1 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        List<List<Integer>> list = new ArrayList<>();
        int sum = 0; // 전체 리프노드 개수
        Queue<Integer> q = new LinkedList<>();
        int[] counts = new int[N];  // 자식 노드 개수
        int[] parents = new int[N];  // 부모 노드

        for(int i = 0; i < N; i++){
            list.add(new ArrayList<>());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(st.nextToken());
            if(num != -1){
                list.get(num).add(i);
                counts[num]++;
            }
            parents[i] = num;
        }

        int K = Integer.parseInt(br.readLine());
        q.add(K);
        if(parents[K] == -1){
            System.out.println(0);
            return;
        }
        counts[parents[K]]--;
        counts[K] = -1;

        while(!q.isEmpty()){
            int now = q.poll();

            for(int next: list.get(now)){
                counts[next] = -1;
                q.add(next);
            }
        }

        for(int i = 0; i < counts.length; i++){
            if(counts[i] == 0) sum++;
        }

        System.out.println(sum);

    }
}

 

 

두 번째 방법

두번째 방법은 DFS를 사용하여 해결하는 방법이다.

DFS를 이용해 노드를 하나씩 들어가다가 탐색 중지 노드를 발견하면 탐색을 멈추는 방식이다.

이때 주의해야 할 점은 탐색을 멈출 때 만약 자식노드가 1개밖에 없는데 그 자식노드가 중지노드라면

멈추기 전에 리프노드의 개수를 한 개 추가해줘야 한다는 것이다.

(위의 그림에서 3번 노드가 원래 없는 노드라고 생각해 보면 이해하기 쉽다.)

 

package boj;

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

public class BOJ1068_2 {
    static int k;
    static int sum = 0;
    static List<List<Integer>> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int root = 0;

        int N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for(int i = 0; i < N; i++){
            list.add(new ArrayList<>());
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(st.nextToken());
            if(num != -1) list.get(num).add(i);
            else root = i;
        }

        k = Integer.parseInt(br.readLine());

        dfs(root);
        System.out.println(sum);
    }

    static void dfs(int num){
        if(num == k) return;
        if(list.get(num).isEmpty()){
            sum++;
            return;
        }

        if(list.get(num).size() == 1){
            int next = list.get(num).get(0);
            if(next != k) dfs(next);
            else sum++;
        }else{
            for(int next: list.get(num)){
                dfs(next);
            }
        }

    }
}