문제 설명

문제 분석

슈도코드

구현

public class 리프노드의개수_1068 {
    static List<Integer>[] tree;
    static boolean[] visited;
    static int result;
    static int deleteNode;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        tree = new ArrayList[N];
        visited = new boolean[N];
        int root = 0;
        for (int i = 0; i < N; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            int parent = scan.nextInt();

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

        deleteNode = scan.nextInt();
        if (deleteNode == root) {
            System.out.println(0);
        } else {
            DFS(root);
            System.out.println(result);
        }
    }

    static void DFS(int num) {
        visited[num] = true;
        int child = 0;
        for (int i : tree[num]) {
            if (!visited[i] && i != deleteNode) {
                child++;
                DFS(i);
            }
        }

        // 자식 노드가 없을 때 리프 노드로 간주
        if (child == 0) {
            result++;
        }
    }
}