[BOJ] 2250번 트리의 높이와 너비

개요

트리를 순회하는 문제, 중위순회를 이용해 탐색하였다.

문제링크

코드

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

public class Baekjoon2250 {
    public static Tree[] trees;
    public static int[] levelLeft;
    public static int[] levelRight;

    public static int n;
    public static int root;
    public static int pos;
    public static int maxLevel;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());

        trees = new Tree[n];
        levelLeft = new int[n];
        levelRight = new int[n];
        maxLevel = 0;

        for(int i=0;i<n;i++) {
            trees[i] = new Tree(i, -1, -1); //트리 초기화
            levelLeft[i] = n+1;
        }

        StringTokenizer st;
        for(int i=0;i<n;i++) {  //입력
            st = new StringTokenizer(br.readLine());

            int value = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            trees[value-1].left = left;
            trees[value-1].right = right;

            if(left != -1)
                trees[left-1].parent = value;
            if(right != -1)
                trees[right-1].parent = value;
        }

        for(int i=0;i<n;i++) {
            if(trees[i].parent == -1)   //루트 노드 탐색
                root = i+1;
        }

        pos = 1;    //현재 열의 위치
        inOrder(root, 1);

        int width = 0;      //너비
        int widthLevel = 1; //너비레벨
        int temp;
        for(int i=0;i<maxLevel;i++) {
            temp = levelRight[i] - levelLeft[i] + 1;    //너비계산

            if(width < temp) {  //계산한 값이 너비보다 크면
                widthLevel = i+1;
                width = temp;
            }
        }

        bw.write(widthLevel+" "+width);
        bw.flush();

    }

    public static void inOrder(int value, int level) {
        Tree node = trees[value-1];

        if(node.left != -1)
            inOrder(node.left, level+1);    //노드의 왼쪽 탐색
        
        levelLeft[level-1] = Math.min(levelLeft[level-1], pos); //기존 값과 pos값 비교
        levelRight[level-1] = pos++;

        if(node.right != -1)
            inOrder(node.right, level+1);   //노드의 오른쪽 탐색

        if(maxLevel < level)    //현재 레벨이 최대레벨보다 크면 최대레벨 갱신
            maxLevel = level;
    }
}

class Tree {
   public int parent;
   public int value;
   public int left;
   public int right;
   
   public Tree(int value, int left, int right) {
       this.parent = -1;
       this.value = value;
       this.left = left;
       this.right = right;
   }

}

해결 과정

처음에는 2차원 배열을 선언해서 하나하나 찾아볼까 했지만 트리 객체를 이용해 너비만 계산해주는 것이 좋을 것같아 방법을 수정하였다.

참고 - https://wooooooak.github.io/algorithm/2018/12/05/백준2250문제/

문제에서 요구하는 것이 같은 레벨에 있는 노드의 제일 왼쪽과 오른쪽의 너비를 계산해서 너비가 제일 큰 레벨과 너비를 출력하는 것인데 그래서 다음과 같은 배열을 만들었다.

public static int[] levelLeft;
public static int[] levelRight;

레벨을 인덱스로 가장 왼쪽, 오른쪽의 열번호를 가지고 있다.

그리고 트리를 입력받아서 트리 객체에 저장하고 중위순회를 해주어야한다.

중위순회는 왼쪽 나자신 오른쪽 순으로 재귀함수로 구현해주었다.

ublic static void inOrder(int value, int level) {
        Tree node = trees[value-1];

        if(node.left != -1)
            inOrder(node.left, level+1);    //노드의 왼쪽 탐색
        
        levelLeft[level-1] = Math.min(levelLeft[level-1], pos); //기존 값과 pos값 비교
        levelRight[level-1] = pos++;

        if(node.right != -1)
            inOrder(node.right, level+1);   //노드의 오른쪽 탐색

        if(maxLevel < level)    //현재 레벨이 최대레벨보다 크면 최대레벨 갱신
            maxLevel = level;
    }

결과