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

노드생성

    static class Node {
        int idx; // 노드 번호
        ArrayList<Node> child = new ArrayList<>();
        public Node(int idx) {
            this.idx = idx;
        }
    }

삭제

    static void deleteNode(int idx) {
        for(Node child : nodes[idx].child) {
            if(child.idx == del) {
                nodes[idx].child.remove(child);
                return;
            }
            deleteNode(child.idx); // 재귀로 삭제
        }
    }

리프노드 찾기

    static void dfs(int idx) {
        //종료
        if (nodes[idx].child.isEmpty()) { // 자식 리스트가 비어있으면 리프노드
            ans++;
            return;
        }

        //확장
        for(Node child : nodes[idx].child) {
            dfs(child.idx);
        }
    }

전체 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Song1068_트리 {
    static int N;
    static int del;
    static int ans;
    static class Node {
        int idx; // 노드 번호
        ArrayList<Node> child = new ArrayList<>();
        public Node(int idx) {
            this.idx = idx;
        }
    }
    static Node[] nodes;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        nodes = new Node[N];

        //각 번호 노드생성
        for (int i = 0; i < N; i++) {
            nodes[i] = new Node(i);
        }

        int root = 0; // 루트 번호를 찾기 위한 변수

        StringTokenizer st = new StringTokenizer(br.readLine());

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

            if (parent == -1) {
                root = i;
                continue;
            }

            nodes[parent].child.add(nodes[i]); // i번 노드의 부모는 parent번 노드
        }

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

        if (del != root) {
            deleteNode(root); // 노드 지우기
            dfs(root); // 리프 노드 갯수 찾기
        }
        System.out.println(ans);

    }

    static void deleteNode(int idx) {
        for(Node child : nodes[idx].child) {
            if(child.idx == del) {
                nodes[idx].child.remove(child);
                return;
            }
            deleteNode(child.idx); // 재귀로 삭제
        }
    }

    static void dfs(int idx) {
        //종료
        if (nodes[idx].child.isEmpty()) { // 자식 리스트가 비어있으면 리프노드
            ans++;
            return;
        }

        //확장
        for(Node child : nodes[idx].child) {
            dfs(child.idx);
        }
    }


}

풀이

• 노드 클래스 만들기
• 삭제 재귀로 구현
• 리프노드 dfs로 카운트
  📌 return 안빼먹기 주의!! 재귀있으면 return 해줘야함!