백준 : 2250

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

2250번: 트리의 높이와 너비

 

트리 구현력과 중위순회를 하면서 cul값을 적절하게 바꾸면 되는 문제다.

연결리스트로 구현하기에는 귀찮은 점이많으므로 3*n 배열을 선언해서 left data right 값을 구현하였다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class B2250 {
    static int N;
    static int parent[];
    static int[][] map;
    static int cur;
    static class BT {
        int left;
        int data;
        int right;
 
        public BT(int left, int data, int right) {
            this.left = left;
            this.data = data;
            this.right = right;
        }
 
    }
    //find
    static int Find(int x) {
        if(parent[x]==x) {
            return x;
        }
        
        return  Find(parent[x]);
    }
    static int Answerh = 0;
    static int Answer = Integer.MIN_VALUE;
    static BT[] node;
    static int deep = 1;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
 
        node = new BT[N + 1];
        parent = new int[N+1];
        
        int left = 0;
        int data = 0;
        int right = 0;
        
        for(int n=1;n<=N;n++) {
            parent[n]=n;
        }
        
        for (int n = 1; n <= N; n++) {
            String[] str = br.readLine().split(" ");
            data = Integer.parseInt(str[0]);
            left = Integer.parseInt(str[1]);
            right = Integer.parseInt(str[2]);
            
            //배열로 2진트리를 구현했다 
            node[data] = new BT(left, data, right);
            
            //root노드 찾기위해서 parent 초기화하기
            if(left!=-1) {
                parent[left] = data;
            }
            
            if(right!=-1) {
                parent[right] =data;
            }
        }
        
        map = new int[2][N+1];
        
        //최상위 노드 찾기
        
        int root = Find(1);
        cur = 1;
        for(int n=1;n<=N;n++) {
            map[0][n] = Integer.MAX_VALUE;
            map[1][n] = Integer.MIN_VALUE;
        }
        
        DFS(2,node[root].left);
        map[0][1] = Math.min(map[0][1], cur);
        map[1][1] = Math.max(map[1][1], cur++);
        DFS(2,node[root].right);
        
        for(int d=1;d<=deep;d++) {
            if(Answer < map[1][d] - map[0][d] +1) {
                Answerh = d;
                Answer = map[1][d] - map[0][d] +1;
            }
        }
        
        System.out.print(Answerh+" "+Answer);
        
    }
 
    public static void DFS(int row, int data) {
        if(data== -1)return;
        deep = Math.max(deep, row);
        DFS(row+1,node[data].left);
        map[0][row] = Math.min(map[0][row], cur);
        map[1][row] = Math.max(map[1][row], cur++);
        DFS(row+1,node[data].right);
    }
}