알고리즘 풀이 - 백준 2250(트리의 높이와 너비, 트리)

 

관련글

 

트리 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

트리의 너비 중 가장 넓은 너비와 해당 너비를 갖는 레벨을 구하는 문제

 

 

2. 풀이

 

이 문제는 트리를 우선 구성하고 중위 순회를 통해 좌측 부터 하나씩 위치를 채워나가는 문제이다.

위치를 채워나가고 나면 각 층위(level)에서의 간격의 최대 / 최소값을 구한 뒤 그 차이가 가장 큰 레벨과 그 간격을 구하여 출력하면 되는 문제이다.

자세한 내용은 코드를 통해 확인하자

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n;
    static Node[] tree;  // 각 노드 정보 저장
    static int pos = 1;  // 최초 시작을 1번위치로 지정
    static int[] min;    // 각 레벨의 위치 중 최소값
    static int[] max;    // 각 레벨의 위치 중 최대값
    static int max_level;
    
    public static void main(String[] args) throws IOException{
    
        // ************************** 주어진 값 저장 ***************************
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        tree = new Node[n+1];
        
        // 레벨은 최대 n+1까지 가능하다. 한 방향으로만 더해지는 경우가 있기 때문
        min = new int[n+1];
        max = new int[n+1];
        
        for(int i=1; i <= n; i++){
            tree[i] = new Node(i);
            min[i] = Integer.MAX_VALUE; // 최소값은 최초에 MAX 값으로
            max[i] = 0;                 // 최대값은 최초에 0으로
        }
        
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            
            int current = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            
            // -1이 아니라면 자식 노드가 있다는 것이므로 그 index를 저장 
            if(left != -1){
                tree[current].left = left;
                tree[left].parent = current;
            }
            
            if(right != -1){
                tree[current].right = right;
                tree[right].parent = current;
            }
        }
        // ************************* 주어진 값 저장 완료 ***********************
        
        
        // ************************* 루트 노드 결정 ****************************
        int root = 0;
        
        // 최초의 root 위치는 주어지지 않았으므로, parent가 지정되지 않은 정점을 root로 지정
        for(int i=1; i <= n; i++){
            if(tree[i].parent == 0){
                root = i;
                break;
            }
        }
        // ************************** 루트 노드 결정 완료 *********************
        
        
        // 중위 순회를 통해 최소 , 최대값을 구한다.
        inOrder(root, 1);
        
        
        // *************************** 최대 간격을 구한다. ********************
        int ans_level = 0;
        int ans_diff = 0;
        for(int i=1; i <= max_level; i++){
        
            // 차이가 가장 큰 부분을 구한다.
            int cur_diff = max[i] - min[i] + 1;
            if(ans_diff < cur_diff){
                ans_level = i;
                ans_diff = cur_diff;
            }
        }
        System.out.println(ans_level + " " + ans_diff);
        // *************************** 최대 간격 구하기 완료 ******************
        br.close();
    }
    
    // 중위 순회를 통해 각 level의 최대 - 최소값의 차이를 구한다.
    private static void inOrder(int num, int level){
        if(tree[num] == null) return;    
        
        max_level = Math.max(level, max_level);
        inOrder(tree[num].left, level+1);
        min[level] = Math.min(pos, min[level]);  // 각 레벨에서 최소, 최대 위치를 찾는다.
        max[level] = Math.max(pos, max[level]);
        pos++;
        inOrder(tree[num].right, level+1);
    }
}

// 노드 정보를 갖는 인스턴스(Class)
class Node{
    int parent = 0;
    int left = 0;
    int right = 0;
    int value;
    public Node(int value){
        this.value = value;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.