[BOJ] 백준 2250번 트리의 높이와 너비 (Java)

#2250 트리의 높이와 너비

난이도 : 골드 2

유형 : 트리 / DFS

2250번: 트리의 높이와 너비

▸ 문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

▸ 입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

▸ 출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

 

문제 풀이  

트리의 너비가 가장 넓은 레벨과 그 레벨의 너비를 구해주면 된다. 열의 기준을 보면 트리 중위 순회가 해당 문제의 본질임을 알아낼 수 있다.

 

구상

열이 밀려나는 규칙을 보면 그 안에 답이 있다. 왼쪽 자식노드는 루트 노드보다 왼쪽에 위치하고 오른쪽 자식 노드는 루트노드보다 오른쪽 열에 위치한다. 결국 가장 왼쪽 자식노드가 1번 열에 위치하게 되고 가장 오른쪽 자식노드가 마지막 열에 위치하게 된다.

 

열과 높이 구하기

중위 순회는 left → root →  right 로 탐색한다. 자세히 보면 탐색하는 순서가 열의 위치와 일치하는 것을 알 수 있다. 따라서 중위순회의 노드 순서가 열이 된다. 

 

중위 순회

 

그럼 이제 탐색 순서를 열의 위치로 저장하고 높이를 구해주면 된다. 

 

높이는 재귀방식을 이용하여 DFS탐색하는 구간에서 왼쪽 자식노드 혹은 오른쪽 자식노드를 탐색할 때 높이를 증가시켜주고 해당 루트노드로 다시 돌아오게 되면 높이를 감소시켜주면 된다.

• 루트노드
  • 왼쪽 자식노드 탐색 height++;
  • 오른쪽 자식노드 탐색 height++;
• 다시 루트노드로 복귀 height--;

 

설계

1. 입력 데이터를 받으며 루트노드를 구해준다. ranks[i] ==0, root = i;
2. 루트노드를 기준으로 중위순회 DFS 탐색을 해준다. traversal(root);
3. 중위순회 순서를 열로, 재귀함수 스택 깊이를 높이로 저장한다.  nodeChart[height].add(row);
4. 각 높이를 오름차순으로 순차적으로 탐색하여 너비를 구해준다.
   1. 너비 = 첫 열 + 끝 열 -1;
5. 너비의 최댓값을 구해준다.
   1. 오름차순으로 탐색하므로 너비가 가장 넓은 레벨이 두 개 있더라도 자연스레 번호가 작은 레벨을 출력한다.

 

해당 문제의 본질인 중위순회 로직은 다음과 같이 표현할 수 있다.

// 중위 순회 
static void traversal(int node) {
	for(Node nxt : list[node]) {
		if(nxt.left != -1) {
			height++; // 재귀 detph+1
			traversal(nxt.left);
		}
		row++; // 중위순회 탐색 순서 count
		nodeChart[height].add(row);
		if(nxt.right!= -1) {
			height++; // 재귀 detph+1
			traversal(nxt.right);
		}
		height--; // 재귀 detph-1
	}
}

 

풀이 코드 

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

public class Main {

	static class Node{
		int left;
		int right;
		
		public Node(int left, int right) {
			this.left = left;
			this.right = right;
		}
	}
	static List<Node>[] list;
	static List<Integer>[] nodeChart;
	static int height=1, row=0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1];
		nodeChart = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
			nodeChart[i] = new ArrayList<>();
		}
		
		int[] ranks = new int[n+1];
		StringTokenizer st = null;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int mid = Integer.parseInt(st.nextToken());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			
			if(left!=-1) ranks[left]++;
			if(right!=-1) ranks[right]++;
			list[mid].add(new Node(left, right));
		}
		
		int root = -1;
		for(int i=1; i<n+1; i++) {
			if(ranks[i]==0) {
				root=i;
				break;
			}
		}
		traversal(root);
		int max = -1, level=0;
		for(int i=1; i<n+1; i++) {
			int len = nodeChart[i].size();
			if(len>0) {
				int s = nodeChart[i].get(0);
				int e = nodeChart[i].get(len-1);
				int width = e-s+1;
					
				if(max < width) {
					max = width;
					level=i;
				}
			}
		}
		System.out.println(level+" "+max);
	}
	
	// 중위 순회 
	static void traversal(int node) {
		for(Node nxt : list[node]) {
			if(nxt.left != -1) {
				height++;
				traversal(nxt.left);
			}
			row++;
			nodeChart[height].add(row);
			if(nxt.right!= -1) {
				height++;
				traversal(nxt.right);
			}
			height--;
		}
	}
}