[백준/BFS] 1068번 트리 (JAVA)

문제

---

풀이

기본적인 BFS 문제였다. Stack과 boolean 배열을 활용해서 풀이했다. 시간복잡도는 O(N^2)이다.

1. removeTargetNode()
   • Stack에 제거할 노드들을 push, pop하면서 자식 노드들을 모두 제거한다.
   • 제거된 노드는 removed에 표시한다.
2. countLeafNode()
   • 제거되지 않은 노드 중, 자식 노드를 갖고 있지 않은 경우 count++한다.

코드

import java.io.*;
import java.util.Stack;

public class Main {

    private static final int ROOT = -1;

    private static int n;
    private static int[] parent;
    private static boolean[] removed;
    private static int target;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        parseInput(br);
        removeTargetNode();
        bw.append(String.valueOf(countLeafNode()));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        parent = new int[n];
        removed = new boolean[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) parent[i] = Integer.parseInt(line[i]);
        target = Integer.parseInt(br.readLine());
    }

    private static void removeTargetNode() {
        Stack<Integer> stack = new Stack<>();
        stack.push(target);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            removed[current] = true;
            for (int i = 0; i < n; i++)
                if (parent[i] == current)
                    stack.push(i);
        }
    }

    private static int countLeafNode() {
        int count = 0;
        for (int i = 0; i < n; i++)
            if (!removed[i] && isLeaf(i)) count++;
        return count;
    }

    private static boolean isLeaf(int current) {
        for (int i = 0; i < n; i++)
            if (!removed[i] && parent[i] == current)
                return false;
        return true;
    }
}