kingsubin

boj)2250 - 트리의 높이와 너비 본문

PS/boj

boj)2250 - 트리의 높이와 너비

kingsubin 2020. 12. 12. 13:19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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 == -1return;
        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;
    }
}
 
cs

 

- 트리

 

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

 

 

 

 


www.acmicpc.net/problem/2250

'PS > boj' 카테고리의 다른 글

BOJ)1389 - 케빈 베이커의 6단계 법칙  (0) 2022.09.24
BOJ)15686 - 치킨배달  (0) 2022.09.22
boj)1991 - 트리 순회  (0) 2020.12.11
boj)7562 - 나이트의 이동  (0) 2020.12.10
boj)11723 - 집합  (0) 2020.12.09
0 Comments
댓글쓰기 폼