[BaekJoon] 2250. # 트리의 높이와 너비

[BaekJoon] 2250. # 트리의 높이와 너비

Question

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

1) 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2) 한 열에는 한 노드만 존재한다.
3) 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4) 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.
이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

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

입력

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

출력

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

Solution

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
    static ArrayList<Node> tree;
    static int width = 1;
    static HashMap<Integer, Integer> nthMinWidth = new HashMap<Integer, Integer>(); 
    static HashMap<Integer, Integer> nthMaxWidth = new HashMap<Integer, Integer>();
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nodeCount = Integer.parseInt(st.nextToken());
        
        // Tree 초기화 
        tree = new ArrayList(nodeCount);
        for (int i = 0; i < nodeCount; i++)
            tree.add(i, new Node(i + 1));
      
        // Tree parent, left, right 지정 
        for (int i = 0; i < nodeCount; i++)
        {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if (left != -1)
            {
                tree.get(left - 1).parent = parent;
                tree.get(parent - 1).left = left;
            }
            if (right != -1)
            {
                tree.get(right - 1).parent = parent;
                tree.get(parent - 1).right = right;
            }
        }
      
        // Root 지정 
        Node root = new Node(0);
        for (Node node : tree) {
            if (node.parent == -1)
                root = node;
        }
      
        // 중위순회하여 각 높이별 최소, 최대 지정 
        inOrder(root.value, 1);
      
        // 최대 너비 확인 
        int maxHeight = 0; 
        int maxWidth = Integer.MIN_VALUE; 
        for (int i = 1; i < nthMaxWidth.size() + 1; i ++)
        {
            // System.out.println(nthMaxWidth.get(i) - nthMinWidth.get(i) + 1);
            if (maxWidth < nthMaxWidth.get(i) - nthMinWidth.get(i) + 1) {
                maxWidth = nthMaxWidth.get(i) - nthMinWidth.get(i) + 1;
                maxHeight = i;
            }
        }
        System.out.println(maxHeight + " " + maxWidth);
    }
    
    private static void inOrder(int value, int height)
    {
        if (tree.get(value - 1).left != -1)
            inOrder(tree.get(value - 1).left, height + 1);
        // width, height 
        nthMinWidth.put(height, Math.min(width, nthMinWidth.getOrDefault(height, Integer.MAX_VALUE)));
        nthMaxWidth.put(height, width);
        width++; 
        if (tree.get(value - 1).right != -1)
            inOrder(tree.get(value - 1).right, height + 1);
    }
}
class Node {
    int parent;
    int value; 
    int left; 
    int right; 
    public Node(int value) {
        this.value = value;
        this.parent = -1;
        this.left = -1;
        this.right = -1;
    }
}

Learning…

• parent, left, right 지정 방식 1) parnet : -1로 초기화 2) 입력받은 값으로 left, right 지정
• nthMinWidth, nthMaxWidth 지정하여 최대값 구하는 방식
• width, height 지정 방식

private static void inOrder(int value, int height)
    {
        inOrder(tree.get(value - 1).left, height + 1);     
        width++; 
  		inOrder(tree.get(value - 1).right, height + 1);
    }

Reference

• BaekJoon