백준 1068번 : 트리 java

이 문제는 트리를 이용하는 문제로 트리를 만들고 노드를 추가, 삭제한 다음 리프 노드의 개수를 세는 문제입니다.

이 문제를 풀 때 조심해야하는 점은 0번이 아닌 다른 노드가 루트 노드가 될 수 있고 이진트리라는 말이 없기 때문에 자식 노드가 3개 이상일 수 있다는 것입니다.

이러한 점 때문에 이 문제에서 쓸 트리를 배열에 저장하는 방식을 통해서 만들었습니다.

parent 배열은 만들어 자신의 부모 노드를 저장할 배열을 만든 후 노드가 제거되면 그 자식 노드까지 제거되도록 dfs를
이용하였습니다.

코드를 바로 보여드리겠습니다.

---

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

public class Main {
    static int N;
    static int[] parent;
    static boolean[] visited;

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

        N = Integer.parseInt(br.readLine());
        parent = new int[N];
        visited = new boolean[N];

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

        int remove = Integer.parseInt(br.readLine());
        removeNode(remove);

        System.out.println(countLeaf());
    }

    static void removeNode(int idx){
        parent[idx] = -2;
        visited[idx] = true;

        for(int i = 0; i<N; i++){
            if(parent[i] == idx)
                removeNode(i);
        }
    }

    static int countLeaf(){
        int sum = 0;

        for(int i = 0; i<N; i++){
            if(visited[i])
                continue;

            if(isLeaf(i))
                sum++;
        }

        return sum;
    }

    static boolean isLeaf(int idx){
        visited[idx] = true;

        boolean leafTrue = true;
        for(int i = 0; i<N; i++){
            if (parent[i] == idx) {
                leafTrue = false;
                break;
            }
        }

        return leafTrue;
    }
}

parent 배열을 순회하며 자신을 부모로 하는 자식 노드가 있다면 leaf가 아니기 때문에 isLeaf를 false로 만들면서 단말 노드인지 확인하였습니다.