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

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

---

각 level 에서 제일 오른쪽에 있는 노드의 x 값에서 제일 왼쪽에 있는 노드의 x을 값을 빼고 +1 을 해주면 너비가 된다.

각 level 의 너비를 비교해서 가장 넓은 너비의 level 과 그 너비를 출력하면 된다.

그러면 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드의 x 값을 알아야 한다.

여기서 트리 구조의inorder 순회 방법을 생각해보자.

inorder 순회에서는 트리의 가장 왼쪽에 있는 노드부터 시작해서 가장 오른쪽에 있는 노드에서 끝난다.

그러면 가장 왼쪽에 있는 노드의 x 좌표를 1로 하고 그 다음에 방문하는 노드의 x 좌표에 +1 씩 해주면서 탐색하면 가장 마지막에 방문하는 노드 즉, 가장 오른쪽에 있는 노드의 x 좌표를 구할 수 있다.

또한 inorder 순회에서 자식 노드로 내려갈 때, level이 하나씩 증가한다.
탐색을 할 때, level 인수도 넘겨줘서 현재 level을 알 수 있고 level 의 가장 왼쪽 x 좌표 가장 오른쪽 x 좌표를 구할 수 있다.

여기서 주의할 점이 하나 더 있는데, 무조건 1 이 루트 노드가 아닐 수 있다.

루트 노드를 찾기 위해 모든 노드의 부모 노드는 -1 로 초기화하여 생성하고 각 값을 입력 받을때 마다 노드의 부모 값을 업데이트 해준다. 그 이후 부모의 값이 -1 인 노드가 루트 노드인 것을 알 수 있다.

---

public class bj2250 {

    public static int N = 0, x, maxLevel;
    public static Node rootNode;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();
    public static ArrayList<Node> tree = new ArrayList<>();
    static int[] levelMinX;
    static int[] levelMaxX;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        levelMaxX = new int[N + 1];
        levelMinX = new int[N + 1];

        // 모든 노드의 부모 -1로 초기화 하여 생성
        for (int i = 0; i <= N; i++) {
            tree.add(new Node(i, null, null));
            // 가장 큰 수로 레벨별 제일 왼쪽의 x 좌표 값 초기화
            levelMinX[i] = N;
        }
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int value = Integer.parseInt(split[0]);
            Node node = tree.get(value);

            int leftValue = Integer.parseInt(split[1]);
            if (leftValue != -1) {
                tree.get(leftValue).parent = value;
                node.left = tree.get(leftValue);
            }

            int rightValue = Integer.parseInt(split[2]);
            if (rightValue != -1) {
                tree.get(rightValue).parent = value;
                node.right = tree.get(rightValue);
            }
        }

		// root 노드 찾기
        for (Node node : tree) {
            if (node.value != 0) {
                if (node.parent == -1) {
                    rootNode = node;
                    break;
                }
            }
        }

		// 가장 왼쪽 노드의 x 좌표 값은 1부터 시작하므로
        x = 1;
        // inorder 순회하면서 찾기 시작 level은 1
        inorder(rootNode, 1);

        int answerLevel = 0;
        int answerWidth = 0;
        for (int level = 1; level <= maxLevel; level++) {
            if (answerWidth < (levelMaxX[level] - levelMinX[level] + 1)) {
                answerWidth = (levelMaxX[level] - levelMinX[level] + 1);
                answerLevel = level;
            }
        }

        sb.append(answerLevel).append(" ").append(answerWidth);

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void inorder(Node node, int level) {
        if (node == null){
            return;
        }
		// 트리의 높이 찾기 위해
        maxLevel = Math.max(level, maxLevel);

		// 왼쪽 자식 노드가 있다며 그 노드로 이동하며 레벨 + 1
        if (node.left != null) {
            inorder(node.left, level + 1);
        }
        // 더 이상 왼쪽 자식 노드가 없어서 현재 노드가 가장 왼쪽의 노드일 때
        levelMinX[level] = Math.min(levelMinX[level], x);
        // 현재 방문한 노드가 현재 레벨에서 가장 큰 x 좌표이므로 (계속 갱신되므로)
        levelMaxX[level] = x;
        // 그 다음으로 탐색하는 노드의 x 좌표는 + 1 이므로
        x++;
        // 왼쪽의 자식노드를 다 탐방하고 오른쪽 자식 노드 탐방
        if (node.right != null) {
            inorder(node.right, level + 1);
        }
    }

    public static class Node {
        int value;
        Node left;
        Node right;
        int parent;

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

}