문제 바로가기

나의 풀이

문제에서 노드를 구현할 필요 없이 list에 자식 노드의 목록을 넣어주는 식으로도 풀 수 있었으나, 노드를 직접 구현해서 tree 구조를 만들어 보려고 다른 분들의 풀이를 조금 참고하여 풀어보았다.

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

class Main {

    static int root;
    static Node[] tree;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tree = new Node[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 0 ~ n-1번의 노드에 각각 주어지는 parent 번호를 입력한 채로 node를 생성하고 tree 배열에 삽입
        for (int i = 0; i < n; i++) {
            int parent = Integer.parseInt(st.nextToken());
            tree[i] = new Node(parent);
            // parent 번호가 -1 인 경우, 해당 노드는 루트 노드
            if (parent == -1) root = i;
        }

        // 루트 노드가 아닌 경우, 해당 노드의 부모 노드를 찾아가 자식 목록에 자신을 추가
        for (int i = 0; i < n; i++) {
            if (root != i) {
                int parent = tree[i].parent;
                tree[parent].addChild(i);
            }
        }

        // 루트 번호를 제거하였다면 0 출력, 아닌 경우 제거 노드의 부모 노드를 찾아가 자식 목록에서 제거한 뒤 루트 노드부터 dfs
        int k = Integer.parseInt(br.readLine());
        if (k == root) {
            System.out.println(0);
        } else {
            int parent = tree[k].parent;
            tree[parent].removeChild(k);
            int leafSize = getLeafSize(root);
            System.out.println(leafSize);
        }
    }

    // dfs 재귀 형식
    static int getLeafSize(int index) {
        if (tree[index].isLeaf()) return 1;
        int sum = 0;
        for (int i = 0; i < tree[index].getChildrenSize(); i++) {
            sum += getLeafSize(tree[index].children.get(i));
        }
        return sum;
    }
}

// 노드 구현
class Node {
    int parent;
    List<Integer> children;

    public Node(int parent) {
        this.parent = parent;
        this.children = new ArrayList<>();
    }

    public void addChild(int child) {
        this.children.add(child);
    }

    public void removeChild(int child) {
        this.children.remove(Integer.valueOf(child));
    }

    public boolean isLeaf() {
        return this.children.isEmpty();
    }

    public int getChildrenSize() {
        return this.children.size();
    }
}