[PS] BOJ2250 트리의 높이와 너비 ( TreeTraversal ) with JAVA

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

◎ 문제풀이

 

트리에서 너비가 가장 넓은 레벨과 레벨의 너비를 구하는 문제이다.  

 

위 그림에 힌트가 있다. 세로축은 레벨을 의미한다. 가로축을 보면 좌측부터 노드의 번호가 매겨진다.

 

8번 노드는 1,

4번 노드는 2,

2번 노드는 3,

14번 노드는 4이다. 

 

가로축을 이용하면 너비를 쉽게 구할 수 있다.

 

레벨2의 2번노드의 가로축 숫자는 3이고 3번 노드의 가로축 숫자는 15이다.

그럼 레벨2의 너비는 15 - 3 + 1, 13이다. 

다시말하여 각 노드를 탐색하면서 각 레벨의 좌측끝 노드와 우측끝 노드의 가로축 숫자를 구하면 되는 문제이다. 

 

가로축 숫자가 매겨지는 순서는 왼쪽 -> 중앙 -> 오른쪽이다. 이는 inorder(중위순회)이다. parent 노드가 중간에서 탐색된다고 하여 중위순회라고 부른다.  그럼 알고리즘은 아래와 같다.

 

1) 노드 테이블에 트리를 구성한다. 

2) 레벨 테이블을 생성한다..

2) 트리를 중위순회로 탐색한다.

3) 노드를 순회하면서 현재 레벨의 좌측끝, 우측끝 노드를 Greedy방식으로 설정한다. 

4) 중위순회가 완료되면 레벨 테이블을 탐색하여 가장 너비가 넓은 레벨을 찾는다.

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//BOJ2250 트리의 높이와 너비
public class Main {

    static Node[] nodes; // 노드 테이블 
    static Level[] levels; // 레벨 테이블

    static int nodePointer = 1; // 가로축 포인터 ( 1 ~ n )
    static int n ;
    static int root;
    public static class Node{
        int parent; // 노드의 부모
        int left; // 노드의 왼쪽 자식
        int right; // 노드의 오른쪽 자식

    }
    public static class Level{
        int leftEnd = n; // 가로축 좌측끝 수
        int rightEnd = 0; // 가로축 우측끝 수
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        nodes = new Node[n+1];
        levels = new Level[n+1];

        // 노드, 레벨 테이블 객체생성
        for(int i=1;i<=n;i++){
            nodes[i] = new Node();
            levels[i] = new Level();
        }

        // 노드 테이블 초기화
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

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

        // 루트 탐색
        for(int i=1;i<=n;i++){
            if(nodes[i].parent==0){
                root = i;
                break;
            }
        }
        
        // 중위순회 시작
        inorder(root,1);

        // 너비가 최대인 레벨 탐색
        int maxCount = 0;
        int maxLevel = 0;
        for(int i=1;i<=n;i++){
            int count = levels[i].rightEnd - levels[i].leftEnd + 1; // 너비 구하기
            if( count > maxCount ){
                maxCount = count;
                maxLevel = i;
            }
        }
        System.out.println(maxLevel+" "+maxCount); // 출력
    }


    // 중위 순회 
    public static void inorder(int root, int level){
        Node currNode = nodes[root]; // 현재 탐색 중인 중간노드

        //왼쪽 서브트리 탐색
        if(currNode.left != -1){
            inorder(currNode.left,level+1);
        }
        
        // 중간노드의 왼쪽서브트리 탐색이 완료되면
        // 레벨의 가로축 좌측끝, 우측끝 데이터 세팅
        // 왼쪽서버트리 탐색을 완료한 상태의 가로축 포인터를 이용.
        levels[level].leftEnd = Math.min(levels[level].leftEnd, nodePointer); // 가로축 포인터가 가리키는 수와 현재 레벨의 좌측끝 가로축 수 비교
        levels[level].rightEnd = nodePointer++; // 좌측 -> 우측 탐색이므로 현재 탐색 중인 노드가 가장 우측끝

        // 오른쪽 서브트리 탐색
        if(currNode.right != -1){
            inorder(currNode.right,level+1);
        }
    }
}