[JAVA] 백준 2250번 【G2.트리의 높이와 너비】

문제

2250번: 트리의 높이와 너비

 

풀이

1️⃣ 중위순회를 이용한 풀이

💡 떠오른 Idea

중위 순회는 위와 같이 트리의 노드를 순회하는 방식이다.

중위 순회를 사용하면 트리에 존재하는 각 노드의 열 값을 알 수 있다.

각 노드의 깊이를 체크해나가면서 중위 순회를 하고, 각 깊이에 해당하는 열 값의 최솟값과 최댓값을 기록해두면 된다.

 

public class Main {
    static Node[] tree;
    static Map<Integer, int[]> info = new HashMap<>();
    static int col = 1;

    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];
        boolean[] isChild = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            tree[i] = new Node(i);
        }

        for (int i = 1; i <= N; i++) {
            String[] input = br.readLine().split(" ");
            int parentNode = Integer.parseInt(input[0]);
            int leftNode = Integer.parseInt(input[1]);
            int rightNode = Integer.parseInt(input[2]);

            if (leftNode != -1) {
                tree[parentNode].leftNode = tree[leftNode];
                isChild[leftNode] = true;
            }

            if (rightNode != -1) {
                tree[parentNode].rightNode = tree[rightNode];
                isChild[rightNode] = true;
            }

        }

        int root = findRoot(N, isChild);

        inOrder(tree[root], 1);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

        for (Integer depth : info.keySet()) {
            int[] value = info.get(depth);
            int width = value[0] - value[1] + 1;
            pq.offer(new int[]{width, depth});
        }

        int[] poll = pq.poll();
        System.out.println(poll[1] + " " + poll[0]);

    }

    private static void inOrder(Node root, int depth) {
        if (root == null) {
            return;
        }

        inOrder(root.leftNode, depth + 1);
        setMaxAndMin(depth);
        col++;
        inOrder(root.rightNode, depth + 1);

    }

    private static void setMaxAndMin(int depth) {
        if (!info.containsKey(depth)) {
            info.put(depth, new int[]{col, col});
        } else {
            int[] maxAndMin = info.get(depth);
            maxAndMin[0] = Math.max(maxAndMin[0], col);
            maxAndMin[1] = Math.min(maxAndMin[1], col);
            info.put(depth, maxAndMin);
        }
    }

    private static int findRoot(int N, boolean[] isChild) {
        int rootNode = 1;
        for (int i = 1; i <= N; i++) {
            if (!isChild[i]) {
                rootNode = i;
                break;
            }
        }
        return rootNode;
    }

    static class Node {
        int value;
        Node leftNode;
        Node rightNode;

        public Node(int value) {
            this.value = value;
        }
    }
}

 

트리의 순회를 하기 전에, 루트 노드를 찾는 방법은 

 

입력 시에, 자식 노드로서 입력되는 노드들을 체크하면 체크되지 않은 유일한 노드가 루트 노드가 됨을 이용하여 찾아내었다.

 

그리고, 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 출력해야하므로, 우선순위 큐를 사용하였다.

 

결과

트리 문제를 풀 때에는, 트리의 성질과 순회의 특성을 잘 파악하는 것이 중요하다는 사실을 다시 한번 깨닫게 되는 문제였다.