백준 1068 - 트리

문제

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

1068번: 트리

 

 

풀이

서브트리를 이용해 문제를 해결한다. 서브트리로 더 이상 나눌 수 없을 때 까지 나누면, 그 때 리프 노드가 된다. 리프 노드는 자식이 더 없으므로 dfs 탐색을 통해서 더 이상 탐색이 불가능 할 때 리프노드로 규정한다.

위 그림에서 3번 노드에서 더 이상 dfs 탐색을 못하므로 3번 노드는 리프 1개가 된다. 4번 노드도 마찬가지로 리프 1개가 된다. 3번과 4번의 부모인 1번 노드에서 이 값들을 더 해준다. 이렇게 1번이 루트인 서브 트리에 대해서 작은 문제를 해결하고, 2번이 루트인 서브 트리에 대해서도 이를 반복하여 큰 문제를 푼다.

 

 

코드

java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int n, x, root;
    static int[] leaf;
    static ArrayList<ArrayList<Integer>> child;

    public static void main(String[] args) {
        input();
        solve();
    }

    private static void solve() {
        for (ArrayList<Integer> a : child) {
            if (a.contains(x))
                a.remove((Integer) x);
        }
        if (root != x)
            dfs(root);
        System.out.println(leaf[root]);
    }

    private static void dfs(int v) {
        if (child.get(v).isEmpty())
            leaf[v] = 1;
        for (int next : child.get(v)) {
            dfs(next);
            leaf[v] += leaf[next];
        }
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        leaf = new int[n];
        child = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            child.add(i, new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            if (v == -1) {
                root = i;
                continue;
            }
            child.get(v).add(i);
        }
        x = sc.nextInt();
        sc.close();
    }
}