[알고리즘] 백준 > #1068. 트리

문제링크

백준 #1068. 트리

풀이방법

이름처럼 트리를 이용하면 해결할 수 있는 문제다! 일단 각 노드에 자식 노드를 저장한다. 입력된 잘린 노드(removedNode)가 자식이라면 그 자식을 children 리스트에서 제거 한 뒤 완전탐색(BFS)을 통해 리프노드를 카운트했다!

간과한 점들 때문에 두번 틀리고 문제를 해결할 수 있었다. 간과한 점들은 다음과 같다.

• 이진트리가 아니다 (설명 어디에도 이진트리란 말은 없다)
• 초기에 leaf 노드가 아니더라도 자식이 잘려나가 leaf 노드가 될 수 있다.

이진 트리가 아니기 때문에 children을 LinkedList 자료구조로 관리했고 완전탐색 시 모든 노드에 대해 leaf 노드가 아닌지 확인(children.isEmpty())을 진행했다.

코드

import java.util.*;
public class BOJ1068 {

    private static Node[] tree;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        tree = new Node[n];
        int[] parentArray = new int[n];
        for (int i = 0; i < n; i++) tree[i] = new Node();

        int rootNode = 0;
        for (int i = 0; i < n; i++) {
            int parent = sc.nextInt();

            if (parent == -1) rootNode = i;
            else tree[parent].children.add(i);
            parentArray[i] = parent;
        }

        int count = 0;
        Integer removedNode = sc.nextInt();
        if (removedNode == rootNode) count = 0;
        else {
            tree[parentArray[removedNode]].children.remove(removedNode);

            Queue<Integer> q = new LinkedList<>();
            q.add(rootNode);

            while (!q.isEmpty()) {
                int head = q.poll();

                if (tree[head].children.isEmpty()) count++;
                else q.addAll(tree[head].children);
            }
        }

        System.out.print(count);
    }
}

class Node {

    public LinkedList<Integer> children;

    public Node() {
        children = new LinkedList<>();
    }
}