[백준] 2250번 트리의 높이와 너비 구하기 (In-Order 사용) : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/2250

2) 문제

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

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

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

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

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

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

3) 입력

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

4) 출력

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

더 자세한 문제의 내용과 제한사항을 보기 위해서는 위의 백준 링크에 들어가서 확인해보자.

2. 풀이

우선 이 문제를 풀기 위해서 필요한 class를 하나 만들어주자

class Node{
    int left, right;
    public int width, depth;
    Node(int left, int right){
        this.left=left;
        this.right=right;
    }
}

Node라는 클래스를 위와 같이 만들어주었고 자식노드를 가리키는 left, right 이외에도 몇 행, 몇 열에 있는지를 나타내는 width와 depth를 추가하였다. width는 가로 몇 번째 칸에 있는지를 나타내는 것이고 depth는 세로, 즉 트리의 높이를 나타내는 것이다.

이 문제는 width를 나타내주기 위해서 무조건 트리의 순회 방법 중 In-Order 방식을 사용해야 한다. 왜냐하면 순회를 할 때 왼쪽 자식 노드부터 순회를 하고 그 다음에 현재 노드, 이후 오른쪽 자식 노드를 순회하기 때문에 width를 기록하기에 가장 좋은 방법이다.

따라서 In-Order 방식으로 구현을 하고 해당 방식을 코드화한 것은 아래와 같다.

static void inorder(int node, int depth){
        if (node==-1) return;
        inorder(arr[node].left, depth+1);
        arr[node].width=++width;
        arr[node].depth=depth;
        inorder(arr[node].right, depth+1);
    }

마찬가지로 -1의 값을 가지고 있으면 return을 하고 왼쪽 자식 노드 -> 현재 노드 -> 오른쪽 자식 노드의 순서로 순회를 한다. 현재 노드 차례에서는 width를 하나씩 늘려가면서 가로 몇번째 칸에 노드가 위치해있는지를 저장하고 depth는 함수의 매개값으로 전달해주어 저장을 하게 된다. 이런식으로 저장하면 모든 노드에 필요한 width와 depth값을 저장할 수 있다.

다음으로는 우리가 트리의 너비를 구해야 하기 때문에 각 depth마다 가장 왼쪽에 위치한 노드와 가장 오른쪽에 위치한 노드의 위치를 알아야한다. 그 두 위치의 차에 +1을 한 것이 너비의 값이라고 한다고 문제에서 주어졌다.

따라서, 각 depth마다 가장 왼쪽과 오른쪽 노드의 위치를 저장해야 하기 때문에

int[] leftmost = new int[10001]; //해당 깊이의 가장 왼쪽 노드
int[] rightmost = new int[10001]; //해당 깊이의 가장 오른쪽 노드

위와 같은 배열을 만들어주고,

int finaldepth=0;
 for(int i=1; i<=n; i++){
   int width=arr[i].width;
   int depth=arr[i].depth;
  finaldepth=Math.max(depth, finaldepth);
 rightmost[depth]=Math.max(rightmost[depth], width);
   if (leftmost[depth]==0){
    leftmost[depth]=width;
}
   else{
  leftmost[depth]=Math.min(leftmost[depth],width);
    }
 }

위와 같이 각 높이마다 가장 왼쪽 노드의 위치와 오른쪽 노드의 위치를 저장해준다. 여기서 가장 깊은 depth가 얼마인지도 추가적으로 알면 최종 계산에서 편하기 때문에 finaldepth라는 수를 만들어서 가장 깊은 높이 또한 구해준다.

3. 코드

이 모든 것을 구현한 코드는 아래와 같다.

import java.util.*;

class Node{
    int left, right;
    public int width, depth;
    Node(int left, int right){
        this.left=left;
        this.right=right;
    }
}
public class Main{
    static int width=0;
    static int n;
    static Node[] arr=new Node[10001];
    static int[] parent = new int[10001];
    static void inorder(int node, int depth){
        if (node==-1) return;
        inorder(arr[node].left, depth+1);
        arr[node].width=++width;
        arr[node].depth=depth;
        inorder(arr[node].right, depth+1);
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=0; i<n; i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int z=sc.nextInt();
            arr[x]=new Node(y,z);
            if (y!=-1){
                parent[y]+=1; //루트를 찾기 위해
            }
            if (z!=-1){
                parent[z]+=1;//루트를 찾기 위해
            }
        }
        int root=0;
        for(int i=1; i<=n; i++){   //루트 노드 구해주는 부분
            if (parent[i]!=1){
                root=i;
            }
        }
        inorder(root, 1);
       
         int[] leftmost = new int[10001]; //해당 깊이의 가장 왼쪽 노드
         int[] rightmost = new int[10001]; //해당 깊이의 가장 오른쪽 노드
        int finaldepth=0;
        for(int i=1; i<=n; i++){
            int width=arr[i].width;
            int depth=arr[i].depth;
            finaldepth=Math.max(depth, finaldepth);
            rightmost[depth]=Math.max(rightmost[depth], width);
            if (leftmost[depth]==0){
                leftmost[depth]=width;
            }
            else{
                leftmost[depth]=Math.min(leftmost[depth],width);
            }
        }
        int ans=0;
        int depthans=0;
        for(int i=1; i<=finaldepth; i++){
            int tmp_ans=rightmost[i]-leftmost[i]+1;
            if (ans<tmp_ans){
                ans=tmp_ans;
                depthans=i;
            }
        }
        System.out.println(depthans+" "+ans);
        
        
    }
}

여기서 하나 중요한 것은 문제에서 root 노드가 1이라고 정확하게 명시되지 않았기 때문에 우리가 루트 노드를 한 번 구해주는 과정이 필요하다는 것이다.

따라서 parent라는 배열을 만들고 문제에서 입력을 받을 때 만약 해당 노드가 자식노드라면 해당 parent 배열의 숫자를 1을 늘린다.

만약 루트 노드가 아니라면 모든 노드는 부모가 1개씩 있을 수밖에 없다. 따라서 전체 노드를 다시 순회하면서 해당 배열의 값이 1이 아닌 것을 찾으면 그것이 루트 노드일 것이다.

문제를 잘 읽고 문제에서 루트 노드가 1로 주어졌는지 아닌지도 잘 살펴보아야 한다.