90. 트리의 높이와 너비 (백준 2250) [JAVA]

 

문제

문제 링크 : https://www.acmicpc.net/problem/1525

1525번: 퍼즐

시간제한	메모리제한	제출	정답	맞은사람	정답비율
2초	128MB	11992	3325	2266	27.177%

문제

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

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

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

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

입력

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

출력

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

 

풀이

처음에 문제를 풀고, 자꾸 에러가 떠서 애먹었던 것은 다음과 같다.

1. 순서가 꼭 1,2,3,4,5 순으로 노드가 들어오는 것이 아니다.
2. 따라서 root가 꼭 1인 것은 아니다.

따라서 입력데이터에서 루트노트를 먼저 찾는다.

 

[1. 루트 찾기]

우선은 값, 부모, 왼쪽, 오른쪽 자식을 가지고 있는 Node 클래스를 선언하고,

어차피 범위가 1~10000까지 이므로 노드들을 저장하는 배열을 선언한다.

값이 정수이기 때문에, 배열의 인덱스를 통해 빠르게 접근할 수 있다.

미리 노드를 만들어놓고, 노드의 입력을 받으면서 자식 노드 - 부모 노드까지 설정해준다.

이후 부모 노드가 없는 노드가 곧 루트가 된다.

 

[2. 중위 순회]

문제는 깊이별로 너비를 구하는 것이다.

그렇다면 너비를 구하는 가장 간단한 방법은, 모든 노드를 왼쪽에 오는 애부터 쭉 줄세우는 방법이다.

왼쪽에 오는 애부터 쭉 줄세우는 것은 곧 중위순회 방문을 의미한다. (L - N - R) 따라서 중위 순회를 구현한다.

 

[3. 깊이 고려]

이때, 우리는 "깊이"별로의 너비를 구해 그 최대값을 찾아야 하기 때문에, 각각의 깊이 역시 기록해두어야 한다.

따라서 각 노드들의 깊이를 저장할 depthMap 배열 역시 선언해준다.

쉽게 쉽게 배열에 저장할 수 있는 이유는 물론 각 노드의 값이 노드의 수 범위내에서 정확히 일치하는 정수이기 때문이다.

또한 가장 깊은 높이인 MaxDepth 역시 구한다. 이는 이후에 정답을 계산하기 용이하기 위해 사용된다.

 

[4.너비 계산]

우리는 깊이의 최대를 알기 때문에 MaxDepth,2만큼의 2차원 배열을 선언한다.

모든 노드들을 중위순회를 통해 왼쪽부터 쭉 정렬시켜놓았기 때문에,

각각의 Depth의 가장 왼쪽 노드와 가장 오른쪽 노드의 순서 (왼쪽에서부터 정렬된 순서)를 저장해준다.

이를 통해 너비를 계산한 뒤 정답을 구해주면 된다.

 

코드

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

//깊이를 알고, inorder로 l - n - r로 탐색하면 왼쪽부터 채울 수 있지 않을까?
//순서는 꼭 1,2,3,4,5 순이 아니다.
//1이 꼭 root는 아니다.

public class Main {
    static int N;
    static Node[] nodes;    
    static ArrayList<Integer> inOrder = new ArrayList<Integer>();

    static int root;

    static int MaxDepth = 0;
    static int[] depthMap;

   public static void main(String[] args) throws IOException{
    StringTokenizer st;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());

    int cur;
    int leftChild;
    int rightChild;

    nodes = new Node[N+1];
    depthMap = new int[N+1];

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

    for(int i=1; i<=N; i++) {
        st = new StringTokenizer(br.readLine());

        cur = Integer.parseInt(st.nextToken());
        leftChild = Integer.parseInt(st.nextToken());
        rightChild = Integer.parseInt(st.nextToken());

        nodes[cur].cur = cur;

        nodes[cur].leftChild = leftChild;
        if(leftChild != -1) {
            nodes[leftChild].parent = cur;
        }


        nodes[cur].rightChild = rightChild;    
        if(rightChild != -1) {
            nodes[rightChild].parent = cur;
        }

    }

    for(int i=1; i<=N; i++) {
        if(nodes[i].parent == -1) {
            root = i;
            break;
        }
    }

    //순회로 채우기
    inorder(root,1);


    //좌우 폭 계산
    int[][] maxWidth = new int[MaxDepth+1][2];
    for(int i=1; i<=N; i++) {
        cur = inOrder.get(i-1);

        if(maxWidth[depthMap[cur]] [0] == 0) {
            maxWidth[depthMap[cur]] [0] = i;
        }

        else {
            maxWidth[depthMap[cur]] [0] = Math.min(i, maxWidth[depthMap[cur]] [0]);
        }    

        maxWidth[depthMap[cur]] [1] = Math.max(i, maxWidth[depthMap[cur]] [1]);
    }

    //정답 계산
    int answer = -1;
    int ansDepth = -1;
    for(int i=1; i<=MaxDepth; i++) {
        int curSize = maxWidth[i][1] - maxWidth[i][0] + 1;

        if(answer < curSize) {
            ansDepth = i;
            answer = curSize;
        }
    }

    System.out.println(ansDepth + " " + answer);

   }

   static void inorder(int cur, int depth) {

       if(cur > -1) {
           MaxDepth = Math.max(MaxDepth, depth);

           //왼
           inorder(nodes[cur].leftChild, depth+1);

           //본인
           inOrder.add(cur);
           depthMap[cur] = depth;

           //오
           inorder(nodes[cur].rightChild, depth+1);
       }

   }
}

class Node{
    public int cur;
    public int leftChild;
    public int rightChild;
    public int parent = -1;

    public Node(int a, int b, int c) {
        this.cur = a;
        this.leftChild = b;
        this.rightChild = c;
    }

    public Node() {}
}

 

결과