[백준-2250]-[트리]-트리의 높이와 너비

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

---

이 문제는 중위 순회법으로 문제를 풀면 된다. 

중위순회법으로 문제를 접근하는 이유는  노드의 위치를 알기위해선 본인 기준 왼쪽에 있는 모든 노드들의 수를 알아야 하기 때문이다. 

그리고 이 문제에서 주의해야 할 점은 1이 무조건 루트가 아니라는거다. 

1이 루트가 아니라는 힌트를 먼저 얻은 다음에 문제에 접근해서 어렵지 않게 문제를 풀었다. 

먼저 Node 클래스를 하나 만들었다. 

class Node{
    int num;
    int left;
    int right;
    int parent;
    
    public Node(int num, int left, int right, int parent) {
        this.num = num;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

어렵게 가지 않기 위해서 부모 노드의 번호도 클래스에 추가시켰다. 

트리의 노드정보를 전부 입력 받은 뒤 parent 값이 초기 값 -1이면 그 노드가 루트라고 정했다.

각 노드는 본인 번호 포함 본인의 좌측, 우측 자식 노드의 번호도 포함한다.

이 값이 -1이면 자식 노드가 없다는 것으로 했다. 

    public static void dfs(int num, int level) {
        Node node = tree[num];
        
        if(maxLevel < level) maxLevel = level;
        
        if(node.left != -1) {
            dfs(node.left, level+1);
        }
        
        levelLeft[level] = Math.min(levelLeft[level], nodeIdx);
        levelRight[level] = nodeIdx++;
        
        if(node.right != -1) {
            dfs(node.right, level+1);
        }
    }

위의 소스가 중위 순회로 트리를 탐색하는 소스이다. 

루트부터 본인의 자식 노드들을 탐색을 한다. 

루트를 기준으로 레벨은 1 이고 그 자식들은 2 그의 자식들은 3 으로 각 노드들의 레벨을 나타냈다. 

maxLevel을 구하는 이유는 레벨이 어디까지 내려갈지 모르기때문에 레벨의 크기를 알기 위함이다.

levelLeft, levelRight는 각 레벨의 제일 좌측 노드와 우측 노드의 번호를 저장하고 그 번호가 각 레벨의 너비를 나타낸다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    public static int root;
    public static int maxLevel, nodeIdx;
    
    public static Node[] tree;
    
    public static int[] levelLeft;
    public static int[] levelRight;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        size = Integer.parseInt(br.readLine());
        
        tree = new Node[size+1];
        levelLeft = new int[size+1];
        levelRight = new int[size+1];
        
        // 초기화
        for(int i=0; i <= size; i++) {
            tree[i] = new Node(i, -1, -1, -1);
            levelLeft[i] = size+1;
        }
        
 
        //입력받기
        for(int i=1; i <= size; i++) {
            st = new StringTokenizer(br.readLine());
            
            int num = Integer.parseInt(st.nextToken());
            int leftNum = Integer.parseInt(st.nextToken());
            int rightNum = Integer.parseInt(st.nextToken());
            
            tree[num].left = leftNum;
            tree[num].right = rightNum;
            
            if(leftNum != -1)
                tree[leftNum].parent = num;
            
            if(rightNum != -1)
                tree[rightNum].parent = num;
        }
        
        // 루트 찾기
        for(int i=1; i <= size; i++) 
            if(tree[i].parent == -1) root = i;
        
        nodeIdx = 1;
        dfs(root, 1);
        
        int res = 1;
        int subs = levelRight[1] - levelLeft[1] + 1;
        
        for(int i=2; i <= maxLevel; i++) {
            int tmpSubs = levelRight[i] - levelLeft[i] +1;
            
            if(subs < tmpSubs) {
                res = i;
                subs = tmpSubs;
            }
        }
        
        System.out.println(res + " " + subs);
    }
    
    public static void dfs(int num, int level) {
        Node node = tree[num];
        
        if(maxLevel < level) maxLevel = level;
        
        if(node.left != -1) {
            dfs(node.left, level+1);
        }
        
        levelLeft[level] = Math.min(levelLeft[level], nodeIdx);
        levelRight[level] = nodeIdx++;
        
        if(node.right != -1) {
            dfs(node.right, level+1);
        }
    }
}
 
class Node{
    int num;
    int left;
    int right;
    int parent;
    int point;
    
    public Node(int num, int left, int right, int parent) {
        this.num = num;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.point = 1;
    }
}