백준 1068 트리(JAVA)

문제 설명

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

 

풀이과정

 List 배열을 이용해서 tree 정보를 저장했다. 그리고 DFS를 통해서 리프 노드의 개수를 더해주도록 풀이했다.

 

정답코드

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

public class Main {

    static int N;
    static List<Integer>[] tree;
    static int root, remove;
    static int result = 0;

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

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());

            if (parent == -1) {
                root = i;
            } else {
                tree[parent].add(i);
            }
        }

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

        if (remove == root) {
            bw.write("0");
            bw.flush();
            return;
        }

        dfs(root);

        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static void dfs(int node) {
        if (node == remove) {
            return;
        }

        int childCnt = 0;
        for (int child : tree[node]) {
            if (child != remove) {
                childCnt++;
                dfs(child);
            }
        }

        if (childCnt == 0) {
            result++;
        }
    }
}