[BOJ] 1068번 - 트리 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

트리의 구조는 부모와 자식의 관계를 가진다.

이 문제에서 입력으로 각 노드의 부모를 입력받기 때문에 부모 노드에 자식 노드를 추가해주었다.

for(int i = 0; i < n; i++) {
    int p = Integer.parseInt(st.nextToken());
    if(p == -1) { //루트노드 저장하기
        root = i;
    }
    else {
        tree[p].add(i); //부모노드에게 자식노드 추가
    }
}

 

이와 같이 저장한 후 전체적으로 DFS를 이용하여 리프노드를 탐색했다.

그러나 여기서 내가 생각하지 못했던 경우가 존재해서 이를 정리해보려고 한다.

 

1. 루트 노드가 리프노드가 되는 경우

• 루트노드가 하나의 자식노드를 가지는데 그 자식 노드를 삭제
• 루트 노드는 리프 노드가 되어 결과가 1이 될 것이다.

2. 루트 노드를 삭제할 경우

• 애초에 탐색을 할 필요가 없다.

처음에는 모든 예제가 맞는데 왜 틀리는지 생각하지 못했다.

그러다가 백준 질문 게시판에서 반례를 아주 쉽게 정리한 글을 보았다.

(https://www.acmicpc.net/board/view/132447)

 

생각해보니 가장 끝의 경우

루트 노드를 생각해보는 것처럼!

이러한 경우를 잘 생각하지 못하는 것 같다.

그래서 앞으로 문제를 보고 경우를 다양하게 생각하는 습관을 들여야겠다.

---

🍀 풀이 🍀

package Baekjoon;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class DFS1068 {
    static ArrayList<Integer>[] tree;
    static int count;
    static int remove;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n];
        count = 0;
        for(int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int root = 0;
        for(int i = 0; i < n; i++) {
            int p = Integer.parseInt(st.nextToken());
            if(p == -1) {
                root = i;
            }
            else {
                tree[p].add(i);
            }
        }

        remove = Integer.parseInt(br.readLine());
        if(root != remove) { //루트노드를 지우지 않으면 탐색 가능
            dfs(root);
        }
        bw.write(count + "");
        bw.flush();
        bw.close();
    }

    static void dfs(int n) {
        boolean flag = false;
        for(int i = 0; i < tree[n].size(); i++) {
            int c = tree[n].get(i);
            if(c != remove) { //지워야하는 노드가 아닐 경우
                dfs(c);
                flag = true;
            }
        }
        if(!flag){
            count++;
        }
    }
}