[백준] 1068번 : 트리 (java)

1068번: 트리 (acmicpc.net)

1068번: 트리

어떻게 생각하고 문제를 풀었는가?

주어진 입력이 i번째 노드의 부모 노드가 몇번째 노드인지 나타내고 있고, 0번째 노드가 루트 노드가 아닐 수 있다는 점, 자식 노드의 수가 정해져 있지 않다는 점을 고려하였습니다.

이를 해결하고자 N개의 노드가 가리키는 부모 노드의 인덱스를 노드 초기화시 저장하고, 모든 노드가 초기화된 후 각 노드가 가리키는 부모 노드의 자식 노드를 추가하도록 하였습니다.

노드의 삭제시 자식 노드에서 해당 노드를 삭제, 리프 노드 계산은 루트 노드에서 시작하여 자식 노드를 dfs로 탐색하도록 하여 문제를 해결할 수 있다고 생각하였습니다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static int N, target, root;
    static Node[] tree;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());
        tree = new Node[N];
        StringTokenizer parentTokenizer = new StringTokenizer(reader.readLine());
        for(int i=0; i<N; i++){
            int parent = Integer.parseInt(parentTokenizer.nextToken());
            tree[i] = new Node(parent);
            if(parent<0) root = i;
        }
        target = Integer.parseInt(reader.readLine());
        reader.close();
        for(int i=0; i<N; i++){
            if(!tree[i].isRoot()){
                int parent = tree[i].parent;
                tree[parent].addChild(i);
            }
        }
        if(target == root){
            System.out.println(0);
        }else{
            int parent = tree[target].parent;
            tree[parent].removeChild(target);
            int leafSize = getLeafSize(root);
            System.out.println(leafSize);
        }
    }

    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();
    }

    public boolean isRoot(){
        return this.parent < 0;
    }
}

Node 클래스를 선언, Node 배열 N개를 초기화하여 i번째 노드에 접근할 수 있습니다.

부모 노드의 인덱스, 자식 노드들의 인덱스를 저장한 후, 배열로부터 이를 찾아 자식노드를 추가하고 리프 노드인지 확인할 수 있습니다.

삭제하려는 노드가 루트 노드라면 모든 노드가 삭제되었으므로 0을 리턴, 루트 노드가 아니라면 해당 노드의 부모 노드로에게 자식 리스트에서 제거하도록 하고, 루트 노드로부터 dfs를 수행합니다.