#백준_1068 트리 - Java 자바

# 유형 : 탐색, 트리

# 맨 처음에는 당연히 이진트리인줄 알고 풀었지만, 이진트리가 아니었다. 그것만 따지면 어렵지 않게 접근할 수 있다. N이 최대가 50이므로 나의 경우에는 어레이리스트를 배열로 선언하여, 연결되는 번호를 다 저장하였고 삭제할 번호를 반복문을 통해 리스트에서 찾아서 제거한 후 해결하였다. 항상 문제를 잘 읽고 풀어야지 하는데 고쳐지질 않는다..

 

 if(arrList[index].size()==1 && next==target)  이 부분은 예를 들어 아래와 같은 경우에 4를 제거하는 경우를 처리해준 것이다.

       0

  1    2   3

       4

 

 

 

 

 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p1068 {
    static int N,target;
    static int cnt=0;
    static int arr[] = new int[51];
    static int start;
    static ArrayList<Integer>[] arrList = new ArrayList[51];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<51; i++)
            arrList[i] = new ArrayList<>();
        
        for(int i=0; i<N; i++) {
            int val = Integer.parseInt(st.nextToken());
            if(val != -1) {
                arrList[val].add(i);
            }else{
                start = i;
            }
        }
        
        target = Integer.parseInt(br.readLine());
        delete();
        if(target!=start) {
            search(start);
            System.out.println(cnt);
        }
        else {
            System.out.println(0);
        }
        
    }
    public static void delete() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<arrList[i].size(); j++)
                if(arrList[i].get(j)==target)
                    arrList[i].remove(j);
        }
    }
    
    public static void search(int index) {
        if(arrList[index].size()==0) {
            cnt++;
            return;
        }
        for(int i=0; i<arrList[index].size(); i++) {
            int next = arrList[index].get(i);
            if(arrList[index].size()==1 && next==target) {
                cnt++;
                return;
            }
            if(next < N && next != target)
                search(next);
        }
    }
}