[BaekJoon] 2250 트리의 높이와 너비 (Java)

1.  문제 링크

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

2.  문제

요약

• 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 합니다.
  1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치합니다.
  2. 한 열에는 한 노드만 존재합니다.
  3. 임의의 노드의 왼쪽 서브트리에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 서브트리에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치합니다.
  4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없습니다.
• 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의합니다.
• 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가합니다.
• 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 정수인 노드의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 주어집니다.
  • 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어집니다.
• 출력: 첫 번째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력합니다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, maxLevel, col;
    static ArrayList<Node> tree;
    static int[] maxCols, minCols;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        maxLevel = 0;
        col = 1;

        tree = new ArrayList<>();
        maxCols = new int[N + 1];
        minCols = new int[N + 1];
        for(int node = 1; node <= N; node++) {
            tree.add(new Node(node));
            maxCols[node] = Integer.MIN_VALUE;
            minCols[node] = Integer.MAX_VALUE;
        }

        for(int node = 1; node <= N; node++) {
            int nodeNum = scanner.nextInt(), left = scanner.nextInt(), right = scanner.nextInt();

            tree.get(nodeNum - 1).left = left;
            tree.get(nodeNum - 1).right = right;

            if(left != -1)
                tree.get(left - 1).parent = nodeNum;

            if(right != -1)
                tree.get(right - 1).parent = nodeNum;
        }
    }

    static void solution() {
        int root = findRoot(tree);

        inOrder(root, 1);

        int maxWidth = Integer.MIN_VALUE, answerLevel = -1;

        for(int level = 1; level <= maxLevel; level++) {
            int width = maxCols[level] - minCols[level] + 1;

            if(maxWidth < width) {
                maxWidth = width;
                answerLevel = level;
            }
        }

        System.out.println(answerLevel + " " + maxWidth);
    }

    static void inOrder(int root, int level) {
        Node rootNode = tree.get(root - 1);

        // 가장 깊은 레벨 갱신
        if(maxLevel < level) maxLevel = level;

        if(rootNode.left != -1)
            inOrder(rootNode.left, level + 1);

        // 현재 level의 가장 왼쪽 x축 값 갱신
        minCols[level] = Math.min(minCols[level], col);
        // 현재 level의 가장 오른쪽 x축 값 갱신
        maxCols[level] = col;
        // 다음 x축 값 계산
        col++;

        if(rootNode.right != -1)
            inOrder(rootNode.right, level + 1);
    }

    static int findRoot(ArrayList<Node> tree) {
        int root = -1;

        for(int node = 1; node <= N; node++) {
            if(tree.get(node - 1).parent == -1) {
                root = node;
                break;
            }
        }

        return root;
    }

    static class Node {
        int nodeNum, left, right, parent;

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

변수 선언 및 초기화

• 각 노드를 표현할 Node 클래스를 생성합니다.
  • 이 클래스는 자신의 번호를 나타내는 nodeNum, 자신의 왼쪽 자식을 나타내는 left, 자신의 오른쪽 자식을 나타내는 right, 자신의 부모를 나타내는 parent를 멤버로 갖습니다.
• maxCols, minCols라는 배열을 생성합니다.
  • minCols
    • 각 level에서 가장 왼쪽에 있는 노드의 x 좌표를 나타냅니다.
    • 정수형의 최댓값으로 값을 초기화합니다.
  • maxCols
    • 각 level에서 가장 오른쪽에 있는 노드의 y 좌표를 나타냅니다.
    • 정수형의 최솟값으로 값을 초기화합니다.
• col이라는 변수를 생성하는데, 이는 이후에 중위 순회를 할 예정인데 중위 순회를 할 때 현재 x좌표를 나타냅니다.
• maxLevel이라는 변수를 생성하는데, 이는 주어진 트리의 최대 level을 저장할 변수입니다.
• 주어진 노드들은 tree라는 ArrayList에 넣어줍니다.

풀이

• 루트 노드를 찾습니다.
  • 루트 노드는 부모 노드가 없기 때문에 부모 노드가 -1인 노드가 루트 노드입니다.
• 중위 순회를 진행하여 각 레벨에서의 가장 왼쪽 노드의 x 좌표와 가장 오른쪽 노드의 x 좌표를 구합니다.
  • 현재 레벨이 maxLevel보다 큰 경우, maxLevel을 갱신해줍니다.
  • 만약 현재 노드의 왼쪽 자식이 있는 경우 왼쪽 자식을 탐색합니다.
  • 만약 왼쪽 자식이 없다면 현재 level의 minCols 값을 확인하여 해당 값이 col 값보다 작다면 현재 level의 minCols 값을 col 값으로 갱신합니다.
  • 현재 level의 maxCols 값을 col 값으로 갱신합니다.
    • 중위 순회는 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 순회를 하는데, 이렇게 순회를 진행하면 x좌표의 값은 증가하는 방향으로만 진행이 될 것이므로 maxCols의 값은 바로 col 값으로 갱신합니다.
  • col의 값을 1 증가시켜 x 좌표 위치를 1 이동시킵니다.
  • 만약 오른쪽 자식이 있다면 오른쪽 자식을 탐색합니다.
• 중위 순회를 진행하고 난 후에는 minLevel과 maxLevel에 각 level의 가장 왼쪽 x 좌표와 가장 오른쪽 x 좌표가 들어있습니다.
• 각 level을 돌면서 너비를 구하고 그 중 너비가 가장 넓은 level을 찾아 이를 출력합니다.