백준(1068번) - 트리

문제 출처: https://www.acmicpc.net/problem/1068

---

문제

• 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

• 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

• 예를 들어, 다음과 같은 트리가 있다고 하자.

• 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

• 이제 리프 노드의 개수는 1개이다.

---

• BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static class Node {

        int vertex;
        Node next;

        public Node(int vertex, Node next) {
            this.vertex = vertex;
            this.next = next;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine()); // 노드의 개수

        Node[] adjList = new Node[N];

        int index = 0;
        int root = 0;

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        while (tokenizer.hasMoreTokens()) {
            int curr = Integer.parseInt(tokenizer.nextToken());

            if (curr == -1) {
                root = index++;
                continue;
            }

            adjList[curr] = new Node(index++, adjList[curr]);
        }

        System.out.println(bfs(adjList, root, Integer.parseInt(reader.readLine())));
    }

    private static int bfs(Node[] adjList, int root, int remove) {
        Queue<Integer> queue = new ArrayDeque<>();

        if (root == remove) return 0;

        queue.offer(root);

        int result = 0;

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            boolean flag = false;

            for (Node node = adjList[curr]; node != null; node = node.next) {
                if (node.vertex == remove) continue;

                flag = true;
                queue.offer(node.vertex);
            }

            if (!flag) result++;
        }

        return result;
    }

}

• DFS + ArrayList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine()); // 노드의 개수

        List<Integer>[] adjList = new List[N];

        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }

        int index = 0;
        int root = 0;

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        while (tokenizer.hasMoreTokens()) {
            int curr = Integer.parseInt(tokenizer.nextToken());

            if (curr == -1) {
                root = index++;
                continue;
            }

            adjList[curr].add(index++);
        }

        int remove = Integer.parseInt(reader.readLine());

        if (root != remove) dfs(adjList, root, remove);

        System.out.println(result);
    }

    private static void dfs(List<Integer>[] adjList, int curr, int remove) {
        boolean flag = false;

        for (int n : adjList[curr]) {
            if (n == remove) continue;

            flag = true;

            dfs(adjList, n, remove);
        }

        if (!flag) result++;
    }

}

---

• 인접 리스트와 BFS를 활용하여 비교적 수월하게 풀 수 있는 문제였다.
• 굳이 BFS를 안쓰고 DFS를 사용해도 풀 수 있을 것 같다.
• 이 문제의 관건은 리프 노드의 개수를 세는 것인데, 처음 인접 리스트에 추가할 때 일부러 부모 → 자식으로 향하는 단방향 리스트로 만들었다. 그래서 특정 노드를 지울 때 굳이 양방향을 생각하지 않고 바로 큐에 삽입을 건너뛰는 것으로 해결할 수 있었다.