[백준] 16652 Binary tree - Java

 

 

 

이진트리니까 트리를 입력받을 때 노드 클래스를 이용해 left와 right를 설정해 주는 방법으로도 풀 수 있지만

간단하게 그래프로 바라보고 풀었다.

 

dfs를 돌리며 높이를 적당히 조절해 주면 된다.

 

 

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

public class Main {
    static int root;
    static ArrayList<Integer>[] list;
    static int N;
    static boolean visit[];

    static int[] arr;    
    static int cnt;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                
        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1];
        list = new ArrayList[N + 1];

        visit = new boolean[N + 1];

        for(int i=0; i<N+1; i++){
            list[i] = new ArrayList<>();
        }
        
        for(int i=1; i<N+1; i++){
            int tmp = Integer.parseInt(br.readLine());
            if(tmp == -1){
                root = i;
                continue;
            }

            list[i].add(tmp);
            list[tmp].add(i);
        }        
        
        dfs(root);
        
        for(int i=1; i<N+1; i++){
            System.out.println(arr[i]);
        }
        
    }

    static void dfs(int node){

        visit[node] = true;
        arr[node] = cnt;        
        cnt++;

        for(int k : list[node]){
            if(!visit[k]){
                dfs(k);             
                cnt--;   
            }            
        }

    }
}