백준 1068 트리 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1068

풀이는 다음과 같다.

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

public class Main {
    static ArrayList<Integer> [] A;
    static int[] answer;
    static boolean[] v;
    static int delete;

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

        int N = Integer.parseInt(br.readLine());
        A = new ArrayList[N+1];
        answer = new int[N+1];
        v = new boolean[N+1];

        for(int i = 0 ; i < N ; i++) {
            A[i] = new ArrayList<>();
        }
        int root = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i++) {

            int a = Integer.parseInt(st.nextToken());
            if(a == -1) {
                root = i;
                continue;
            }

            A[i].add(a);
            A[a].add(i);
        }

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

        //노드를 지웠을 때, 리프 노드의 개수를 출력한다.
        v[root] = true;
        dfs(root);
        
        int a = answer[root];
        if(root == delete) a = 0;
        bw.write(String.valueOf(a));
        bw.flush();
        bw.close();






    }
    static void dfs(int from) {

        int baby = 0;
        for(int to : A[from]) {
            if(!v[to]) {
                if(to == delete) continue;
                v[to] = true;
                baby++;
                dfs(to);
                answer[from] += answer[to];
            }
        }
        if(baby == 0) answer[from] = 1;
    }


}

dfs 로직을 알고 있다면, 충분히 풀 수 있는 문제이다.

우리는, 어떠한 트리 구조에서
어떤 노드를 제거했을때의 리프 노드의 수를 구하면 된다.

풀이에서 핵심 요소는 다음과 같다.

1. 리프노드는, 자식노드가 없는 노드를 의미하므로,
   리프노드를 체크하기 위해 dfs안에 baby(자식노드의 수) 를 넣었다.
   만약 자식노드가 한개도 없다면, 리프노드이므로 체크를 해주었다.

dfs함수 안에
int baby = 0;

to 라는 자식이 하나 있을때마다 
baby++;

만약 자식이 없다면 리프노드이므로, 리프노드 하나이다 라고 체크해주기
if(baby == 0) answer[from] = 1;

2. dfs 함수에서 부모노드 from 에서 자식노드 to를 돌때, 빠져나오며 자식노드들의 리프노드의 수를 더해주는 로직이 필요하다.

answer[from] += answer[to];

3. dfs함수 안에서, 제거 노드에 도달시, 더이상 깊게 들어가지 않고 제껴버린다.

if(to == delete) continue;