BOJ2250 트리의 높이와 너비 java

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

힌트 1

• 중위 순회는 X축을 기준으로 왼쪽부터 방문한다는 특징이 있다.
• 그러므로 너비를 구하려면 중위순회를 이용하면 된다.
• 중위 순회를 이용하되, 추가적으로 Level 값을 저장하도록 하여 문제를 해결할 수 있다.

루트 찾기

• 루트가 1이라고 문제에 없기 때문에 루트를 찾아줘야 함
• Node Class에 parent의 여부를 가지고 있어서 parent가 없는 노드가 root node

실수

• 같은 레벨인 값을 List로 가지고 있다가 정렬 후 첫 번째 원소와 마지막 원소를 통해서 너비를 구했다.
• 92%에서 실패를 하는걸보니 반례가 있었나보다.
• minLevel, maxLevel 배열을 통해서 구해줬더니 통과했다!

Map<Level, List<Count>> 코드는 이 코드를 짠 시간이 아쉬워서 주석처리만 했다.

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

public class Main {
    static Map<Integer, Node> map;
    static int  count = 0;
    static int level = 0;
    static int[] levelMin;
    static int[] levelMax;
    // static Map<Integer, List<Integer>> levelMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.valueOf(st.nextToken());
        map = new HashMap<>();
        // levelMap = new HashMap<>();
        levelMin = new int[N+1];
        levelMax = new int[N+1];

        for(int i = 1 ;i<=N;i++) {
            st = new StringTokenizer(br.readLine());
            int root = Integer.valueOf(st.nextToken());
            int left = Integer.valueOf(st.nextToken());
            int right = Integer.valueOf(st.nextToken());
            map.put(root, new Node(root, left, right));
            levelMin[i] = N;
        }

        // 루트 구하기
        int root = getRoot(map);

        inOrder(map.get(root));

        int maxWidthLevel = 1;
        int maxWidth = levelMax[1] - levelMin[1] + 1;
        for(int i = 2;i<=N;i++) {
            int width = levelMax[i] - levelMin[i] + 1;
            if(maxWidth < width) {
                maxWidthLevel = i;
                maxWidth = width;
            }
//        for(Map.Entry<Integer, List<Integer>> entry : levelMap.entrySet()) {
//            int key = entry.getKey();
//            List<Integer> values = entry.getValue();
//            if(values.size() == 1) continue;
//            Collections.sort(values);
//            int width = values.get(values.size()-1) - values.get(0) + 1;
//            if(width > maxWidth) {
//                maxWidthLevel = key;
//                maxWidth = width;
//            } else if(width == maxWidth) {
//                if(key < maxWidthLevel) {
//                    maxWidthLevel = key;
//                    maxWidth = width;
//                }
//            }
        }

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

    private static int getRoot(Map<Integer, Node> map) {
        for(Map.Entry<Integer, Node> entry : map.entrySet()) {
            Node node = entry.getValue();
            if(node.left != -1) {
                map.get(node.left).parent = true;
            }
            if(node.right != -1) {
                map.get(node.right).parent = true;
            }
        }

        for(Map.Entry<Integer, Node> entry : map.entrySet()) {
            Node node = entry.getValue();
            if(!node.parent) return entry.getKey();
        }
        return 0;
    }
    private static void inOrder(Node node) {
        level++;
        if (node.left != -1) {
            inOrder(map.get(node.left));
        }
        // System.out.println("root : " + node.root + " level : " + level + " count : " + count);
//        if(!levelMap.containsKey(level)) {
//            levelMap.put(level, new ArrayList<>());
//        }
        levelMin[level] = Math.min(levelMin[level], count);
        levelMax[level] = count++;
        //levelMap.get(level).add(count++);
        level--;
        if (node.right != -1) {
            level++;
            inOrder(map.get(node.right));
            level--;
        }
    }

    static class Node {
        boolean parent;
        int root;
        int left;
        int right;

        Node(int root, int left, int right) {
            this.parent = false;
            this.root = root;
            this.left = left;
            this.right = right;
        }
    }
}