[BOJ] 백준 [1068] 트리 JAVA

문제

 

풀이

 

생각보다 간단한 문제이다 . 끊어질 노드를 C 라고 하자. 그래프를 ArrayList 배열로 만든 뒤

끊어질 노드'C'의 위치까지 처음부터 다 받아서 그래프를 단방향으로 연결할 때 C가 나오면 

연결을 안 해주면 끝. 
root 부터 DFS 돌리면서 ArryList의 size가 0이면 leaf 노드이다.

 

입력 노드'e' 를 받을때 3가지의 경우로 나눌 수 있는데

1. e 가 root 일때 => e == -1

2. e 가 끊어질 노드 'C' 이거나 연결하려는 노드의 부모노드가 'C'일때 => ( e==C || i ==C )

3. 그외 경우엔 단방향 연결 

 

단방향으로 연결이 완성된 그래프를 root 부터 DFS 재귀호출을 이용하여 자식이 없는 노드를 카운트하면 끝.

이때 , 끊어질 노드 'C'가 root 이면 leaf노드는 없으므로 예외처리.

 

 

import java.util.*;
import java.io.*;
import java.time.LocalDateTime;
 
 
public class Main{
 
    static int N,C,cnt;
    static ArrayList<Integer>[] list;
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N];
        for(int i=0;i<N;i++)
            list[i] = new ArrayList<Integer>();
        
        String[] input = br.readLine().split(" ");
        C = Integer.parseInt(br.readLine());
        
        int root=-1;
        for(int i=0;i<N;i++) 
        {
            int e = Integer.parseInt(input[i]);
            if(e==-1)
                root = i;
            else if(e == C || i==C )
                continue;
            else 
                list[e].add(i);
        }
        if(root==C)
            cnt=0;
        else 
            DFS(root);
     
        System.out.println(cnt);
    }
    
    static void DFS(int x) {
        if(list[x].size()==0){
            cnt++;
            return;
        }
        for(int e : list[x])
            DFS(e);
    }
}