BOJ_1068 : 트리

👉 문제링크

1068번: 트리

---

---

🔸 문제 분석 🔸

• 트리의 루트 노드와 각 인덱스 별 노드의 부모 노드 정보가 입력된다.
  • 한 노드를 지우면 아래 자손 노드들이 모두 지워진다.
  • 남은 리프노드의 수를 출력한다.
• 인접 리스트를 만들어 연결 정보를 저장한다.
  • 만약 아직 부모노드가 등장하지 않았다면, 큐에 넣고 순서를 기다린다.
• 삭제할 때  DFS를 사용해 자식 노드를 모두 삭제한다.

🔸 코드 🔸

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

public class Main {
    private static int N, cnt;
    private static ArrayList<Integer>[] adjList;

    private static void dfs_delete(int target) {
        while (adjList[target].size() > 0) {
            dfs_delete(adjList[target].get(0));
            adjList[target].remove(0);
        }
        adjList[target] = null;
    }

    private static class Pair {
        int i, num;

        public Pair(int i, int num) {
            this.i = i;
            this.num = num;
        }
    }

    private static void print() {
        System.out.println("=========================");
        for (ArrayList<Integer> arr : adjList) {
            System.out.println(arr);
        }
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        adjList = new ArrayList[N];

        Queue<Pair> queue = new ArrayDeque<>();
        int start = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            if (num == -1) {
                start = i;
                adjList[i] = new ArrayList<>();
            } else if (adjList[num] != null) {
                adjList[num].add(i);
                adjList[i] = new ArrayList<>();
                adjList[i].add(num);
            } else {
                queue.add(new Pair(i, num));
            }
        }

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int num = pair.num;
            int i = pair.i;
            if (adjList[num] != null) {
                adjList[num].add(i);
                adjList[i] = new ArrayList<>();
                adjList[i].add(num);
            } else {
                queue.add(new Pair(i, num));
            }
        }

//        print();

        // Delete node
        cnt = 0;
        int target = Integer.parseInt(br.readLine());
        if (target != start) { // 부모 노드가 있으면, 부모 노드에서 타겟 삭제
            adjList[adjList[target].get(0)].remove(Integer.valueOf(target));

            for (int i = 0; i < N; i++) { // 루트 노드가 아니면, 부모노드 정보 삭제
                if (i != start)
                    adjList[i].remove(0);
            }

            dfs_delete(target);

            for (ArrayList<Integer> arr: adjList) {
                if (arr != null && arr.size() == 0) cnt++;
            }
        }
//        print();

        // Output
        System.out.println(cnt);
    }
}

🔸 코드 해석 🔸

• 인접 리스트 adjList에 트리 정보를 저장한다.
  • 아직 부모가 만들어지지 않았다면 큐에 넣고 기다린다.
• 노드 삭제 연산을 수행한다.
  • 루트 노드를 삭제하면 계산할 것도 없이 0을 출력한다.
  • 부모노드가 있으면 부모 노드 자식 정보에서 현재 타겟 노드를 지운다.
  • 타겟 노드의 자식들을 dfs로 모두 삭제해 준다.
  • adjList에서 null이 아닌(노드가 존재) 상태이며, 자식 노드의 수가 0이면 리프노드이므로 카운트한다.
• cnt를 답을 출력한다

---

🔸 end 🔸

• union find 알고리즘 문제인 줄 알았지만, dfs로 풀이할 수 있었다.