[백준 알고리즘] 1068번 트리(Java) 문제 풀이

문제

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

1068번: 트리

문제에 대한 이해

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

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

리프 노드의 갯수를 찾는 문제이다.

어떻게 풀 것인가?

주어진 트리에서 그래프 탐색을 이용하여, 리프노드의 갯수를 찾아야한다.

물론 그 이전에 트리를 구성하고, 지울 노드의 수를 입력받아 해당 노드와 자식 노드를 삭제해야한다.

 

처음에는 삭제할 노드도 리프노드의 갯수도 DFS로 처리해야겠다고 생각했다. 하지만 이 문제는 BFS, DFS를 모두 사용한 방법을 물어보는 문제였다. 

풀면서 놓쳤던점

처음에 자료구조를 무엇을 사용해야할지 많이 고민했던 것 같다. 그와 관련하여 시간을 많이 잡아먹었다.

또한 BFS와 DFS의 차이에 대한 정확한 파악이 부족했다. 

이 문제를 통해 얻어갈 것

DFS와 BFS의 활용

내 코드 

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

// 백준알고리즘 1068번 트리

public class Main {
    static int N, deleteNum;

    static List<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        list = new ArrayList[N];

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

        int root = -1;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (num == -1) {
                root = i;
                continue;
            }
            list[num].add(i);
        }

        int deleteNum = Integer.parseInt(br.readLine());

        DFS(deleteNum);
        if (deleteNum == root) {
            System.out.println(0);
        } else {
            System.out.println(BFS(root));
        }

    }

    static void DFS(int node) {
        if (list[node].size() > 0) {
            int size = list[node].size();
            while (size > 0) {
                int child = list[node].get(--size);
                DFS(child);
            }
        }

        for (int i = 0; i < N; i++) {
            if (list[i].contains(node)) {
                for (int j = 0; j < list[i].size(); j++) {
                    if (list[i].get(j) == node) {
                        list[i].remove(j);
                    }
                }
            }
        }
    }

    static int BFS(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        int cnt = 0;

        while (!q.isEmpty()) {
            int pos = q.poll();
            if (list[pos].size() == 0) {
                cnt++;
                continue;
            }
            for (int next : list[pos]) {
                q.add(next);
            }
        }
        return cnt;
    }
}