kingsubin

import java.io.*;
import java.util.StringTokenizer;
 
public class boj_2250 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int order = 0;
    static int[] cnt, left, right;
    static Node[] a;
 
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        a = new Node[n+1];
        cnt = new int[n+1];
        left = new int[n+1];
        right = new int[n+1];
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
 
            a[x] = new Node(y, z);
            if (y != -1) cnt[y] += 1;
            if (z != -1) cnt[z] += 1;
        }
 
        // left, right 추가하면서 cnt에 부모가 존재하는지 체크
        // cnt에서 값이 0 이라면 부모가없고 루트로 볼 수 있다.
        int root = 0;
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == 0) {
                root = i;
            }
        }
 
        // 열의 순서는 inoroder한 순서와 같다.
        inorder(root, 1);
 
        // 최대 depth와 해당 depth 에서의 최소 order, 최대 order
        int maxdepth = 0;
        for (int i = 1; i <= n; i++) {
            int depth = a[i].depth;
            int order = a[i].order;
            if (left[depth] == 0) {
                left[depth] = order;
            } else {
                left[depth] = Math.min(left[depth], order);
            }
            right[depth] = Math.max(right[depth], order);
            maxdepth = Math.max(maxdepth, depth);
        }
 
        // ans
        int ans = 0;
        int ans_level = 0;
        for (int i = 1; i <= maxdepth ; i++) {
            if (ans < right[i] - left[i] + 1) {
                ans = right[i] - left[i] + 1;
                ans_level = i;
            }
        }
        System.out.println(ans_level + " " + ans);
    }
 
    static void inorder(int node, int depth) {
        if (node == -1) return;
        inorder(a[node].left, depth + 1);
        a[node].order = ++order;
        a[node].depth = depth;
        inorder(a[node].right, depth + 1);
    }
}
 
class Node {
    int left;
    int right;
    int order;
    int depth;
 
    public Node(int left, int right) {
        this.left = left;
        this.right = right;
    }
}
 

 

- 트리

 

- inorder 활용해서 열 번호 구하는것도 생각 못했고 구현하기도 어렵다.

 

 

 

 

---

www.acmicpc.net/problem/2250