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

문제 출처

사용 언어: Java

1. 구상

• 입력받는 노드 번호, 왼쪽 자식, 오른쪽 자식을 저장
  → Node 클래스를 만들어 노드 번호, 왼쪽 자식, 오른쪽 자식, 부모 노드 번호를 저장

• 배열을 확인하면 중위순회 순서 (왼쪽 > 루트 > 오른쪽)로 열 번호가 설정되어 있음.
  

• level (행 번호)마다 가장 왼쪽에 있는 노드의 열 값이 최소이고 가장 오른쪽에 있는 노드 열 값은 최대
  → 각 열마다 가장 왼쪽에 있는 노드 열 번호를 min 배열에 저장, 가장 오른쪽에 있는 노드 열 번호는 max 배열에 저장
  → 중위순위하면서 level의 min과 max를 초기화 하기

알고리즘 및 코드 참고 링크

2. 구현

import java.util.*;
import java.lang.*;
import java.io.*;

public  class Main {	
	
	static Node[] tree;
	//왼쪽열은 min, 오른쪽열은 max
	static int[] max, min;
	//노트 열 1부터
	static int nodeCol = 1;
	
	public static void main(String[] args) throws NoSuchElementException, IOException {
		Scanner s = new Scanner(System.in);		
		
		int n = s.nextInt();
		tree = new Node[n+1];
		int root = 0;
		min = new int[n+1];
		max = new int[n+1];
		
		int maxLevel = 1; //최대 너비를 가지는 레벨
		int maxWidth = 0; //최대 너비 길이
		
		 //트리와 min,max배열 초기화
		for(int i=0;i<=n;i++) {
			tree[i]=new Node(i,-1,-1);
			min[i] = n;
			max[i] = 0;
		}
		
		for (int i = 1; i <= n; i++) {
			int num = s.nextInt();
			int left = s.nextInt();
			int right = s.nextInt();
			
			tree[num].left = left;
			tree[num].right = right;
			
			/*왼쪽, 오른쪽 자식이 있다면 자식의 부모 노드를 
            현재 노드로 설정*/
			if (left != -1)
				tree[left].parent = num;
			if (right != -1)
				tree[right].parent = num;
		}
		
		//부모 노드가 없다면 root로
		for (int i = 1; i <=n; i++) {
			if (tree[i].parent == -1) {
				root = i;
				break;
			}
		}
		
		inorder(root, 1);
		
        //최대 너비를 가지는 level과 너비 길이 구하기
		for (int i = 0; i <= n; i++) {
			int tmp = max[i] - min[i];
			
			if (maxWidth < tmp) {
				maxLevel = i;
				maxWidth = tmp;
			}
		}
		
		System.out.println(maxLevel + " " + (maxWidth + 1));
	}
	
	
	static class Node{
		int num; //노드 숫자
		int parent; //노드의 부모 (없으면 -1)
		int left; //노드 왼쪽 자식
		int right; //노드 오른쪽 자식
		
		Node(int num,int left,int right){
			this.num = num;
			this.parent = -1;
			this.left = left;
			this.right = right;
		}
	}
	
	//중위 순위
	static void inorder(int root, int level) {
		Node cur = tree[root];
		//왼쪽 자식 방문
		if (cur.left != -1)
			inorder(cur.left, level+1);
		
		//루트 방문 (nodeCol은 현재 열번호)
		min[level] = Math.min(min[level], nodeCol);
		max[level] = Math.max(max[level], nodeCol);
		nodeCol++;
		
		//오른쪽 자식 방문
		if (cur.right != -1)
			inorder(cur.right, level + 1);
	}

}