[알고리즘] 백준 > #2250. 트리의 높이와 너비

문제링크

백준 #2250. 트리의 높이와 너비

풀이방법

트리문제다! 문제에 주어진 아래 그림을 보면서 이리저리 생각해봤다.

왼쪽으로 쭉~ 들어가 가장 왼쪽에 있는 노드부터 찾아야 겠다는 생각을 했다. 그러다보니 중위순회가 생각이 났다. 중위순회로 노드들은 방문하니 각 노드에 col index를 매길 수 있었다. 그리고 각 level 내 노드들의 col index를 저장해 모든 level의 width를 구해 문제를 해결했다!

✔️ root노드는 1이 아닐 수 있다!!

코드

import java.util.*;

public class BOJ2250 {

    static final int NO_CHILD = -1;

    static int colCount = 1;
    static TreeNode[] tree;
    static LinkedList<Integer>[] levels;
    static boolean[] rootCheck;

    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        tree = new TreeNode[n + 1];
        levels = new LinkedList[n + 1];
        rootCheck = new boolean[n + 1];
        for (int i = 1; i <= n; i++) rootCheck[i] = true;

        for (int i = 1; i <= n; i++) {
            int node = sc.nextInt();
            int leftChild = sc.nextInt();
            int rightChild = sc.nextInt();

            tree[node] = new TreeNode(leftChild, rightChild);
            if (leftChild != NO_CHILD) rootCheck[leftChild] = false;
            if (rightChild != NO_CHILD) rootCheck[rightChild] = false;

            levels[i] = new LinkedList();
        }

        setColInfo(getRootNode(n), 1);

        int maxWidth = 0;
        int level = 0;
        for (int i = 1; i <= n; i++) {
            if (levels[i].isEmpty()) break;

            Collections.sort(levels[i]);

            int width = levels[i].getLast() - levels[i].getFirst() + 1;
            if (maxWidth < width) {
                maxWidth = width;
                level = i;
            }
        }

        System.out.print(level + " " + maxWidth);
    }

    static private void setColInfo(int node, int depth) {
        if (tree[node].leftChild != NO_CHILD) setColInfo(tree[node].leftChild, depth + 1);
        tree[node].col = colCount++;
        levels[depth].add(tree[node].col);
        if (tree[node].rightChild != NO_CHILD) setColInfo(tree[node].rightChild, depth + 1);
    }

    static private int getRootNode(int n) {
        for (int i = 1; i <= n; i++) if (rootCheck[i]) return i;
        return -1;
    }
}

class TreeNode {
    public int leftChild;
    public int rightChild;
    public int col;

    public TreeNode(int leftChild, int rightChild) {
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}