[Do It! 코딩테스트 자바편(김종관)] 문제 068(백준 1068번)

느낀점

• 내가 풀려면 안 떠오르는데 교재 풀이 보면 바로 이해할 수 있는 문제

문제

트리(백준: 1068번)

풀이

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int nodeCnt, delNode, result = 0;
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        nodeCnt = sc.nextInt();
        for (int i = 0; i < nodeCnt; i++)
            tree.add(new ArrayList<>());
        visited = new boolean[nodeCnt];

        int rootNode = 0;
        for (int i = 0; i < nodeCnt; i++) {
            int parent = sc.nextInt();
            if (parent != -1) {
                tree.get(i).add(parent);
                tree.get(parent).add(i);
            } else
                rootNode = i;
        }
        delNode = sc.nextInt();

        if (rootNode == delNode)
            System.out.println(0);
        else {
            dfs(rootNode);
            System.out.println(result);
        }
        sc.close();
    }

    private static void dfs(int now) {
        visited[now] = true;
        int childCnt = 0;

        for (int next : tree.get(now)) {
            if (!visited[next] && next != delNode) {
                childCnt++;
                dfs(next);
            }
        }

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

}