[백준] 2250: 트리의 높이와 너비 - JAVA

in Algorithm on 그래프 이론

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

풀이

트리를 격자모양의 틀에 넣을 때 트리의 깊이별로 너비를 구했을 때 최댓값을 찾는 문제.

입력받으면서 트리를 저장하는데, 부모, 왼쪽 자식, 오른쪽 자식을 저장한다.

입력받아서 저장한 후 부모가 -1로 되있는 것이 루트 노드이다.

루트노드부터 중위순회(왼쪽 - 루트 - 오른쪽)하여 탐색하면 열 번호를 1부터 순서대로 부여할 수 있다.

중위순회할 때 트리의 깊이(level)도 함께 넘겨 각 깊이별로 열 번호의 최대와 최소를 저장한다.

중위순회를 마친 후 깊이별로 너비의 최댓값을 구한다.

메모리: 21176KB

시간: 256ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int num;
        int parent;
        int left;
        int right;

        public Node(int num, int left, int right) {
            this.num = num;
            this.left = left;
            this.right = right;
            this.parent = -1;
        }
    }

    static Node[] tree;
    static int[] max, min;
    static int idx, maxLevel;

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

        tree = new Node[N + 1];
        max = new int[N + 1];
        min = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            tree[i] = new Node(i, -1, -1);
            max[i] = 0;
            min[i] = N + 1;
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            tree[num].left = left;
            tree[num].right = right;

            if (left > 0) {
                tree[left].parent = num;
            }
            if (right > 0) {
                tree[right].parent = num;
            }
        }

        int root = 0;
        for (int i = 1; i < N + 1; i++) {
            if (tree[i].parent == -1) {
                root = i;
            }
        }

        idx = 1;
        maxLevel = 0;
        inOrder(root, 1);

        int ansLevel = 0;
        int ansWidth = 0;
        for (int i = 1; i <= maxLevel; i++) {
            int width = max[i] - min[i] + 1;
            if (ansWidth < width) {
                ansLevel = i;
                ansWidth = width;
            }
        }

        System.out.println(ansLevel + " " + ansWidth);
    }

    private static void inOrder(int num, int level) {
        Node node = tree[num];

        if (node.left > 0) {
            inOrder(node.left, level + 1);
        }

        maxLevel = Math.max(maxLevel, level);
        max[level] = Math.max(max[level], idx);
        min[level] = Math.min(min[level], idx);
        idx++;

        if (node.right > 0) {
            inOrder(node.right, level + 1);
        }
    }

}