[Java/자바] - 백준(BOJ) 1068번 : 트리

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

1068번: 트리

 

ArrayList에 관계를 저장 후DFS를 통해 탐색하며

리프노드인지 확인하는데 delete된 노드인지 확인하는 프로세스를 추가한다.

리프노드일 경우 전역변수 count를 증가시킨다.

 

import java.util.*;
public class Main {
    static int count = 0;
    static int n, del;
    static int start;
    static ArrayList<Integer>[] arr = new ArrayList[50];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i=0; i<50; i++)
            arr[i] = new ArrayList<>();

        int k;
        for (int i=0; i<n; i++) {
            k = sc.nextInt();
            if (k == -1)
                start = i;
            else
                arr[k].add(i);
        }
        del = sc.nextInt();
        if (del != start)
            search(start);
        System.out.println(count);
    }
    public static void search(int index) {
        if (arr[index].size() == 0){
            count++;
            return;
        }
        for (int i=0; i<arr[index].size(); i++){
            int next = arr[index].get(i);

            if (arr[index].size() == 1 && next == del) {
                count++;
                return;
            }

            if (next < n && next != del)
                search(next);

        }
    }
}