BJ_G2_2250_트리의 높이와 너비 - Java

[문제링크]

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

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]

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

---

[예제 출력 1]

3 18

 

---

[설명]

이 문제는 이진트리를 구현하고 중위순회를 확인하는 문제이다.

Node를 만들어서 Node로 이루어진 Tree 배열을 생성하여 값들을 넣어준다.

트리의 가장 왼쪽부터 번호가 시작되므로 중위순회를 해야한다.

중위순회에서는 각 레벨에서 최소의 인덱스 값과 최대의 인덱스 값을 찾아야한다. 

레벨별로 가장 그 차이가 큰 값을 출력해주면 된다.

 

 

백준 알고리즘 2250번 JAVA풀이

 

import java.util.Scanner;

public class Main {

	static Node[] tree;			//tree
	static int[] min,max;		//각 레벨별 최소, 최대값을 저장
	static int lv=1;			//레벨은 1부터 존재
	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		int N=scann.nextInt();
		tree=new Node[N+1];
		min=new int[N+1];
		max=new int[N+1];
		int root = 0;
		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++) {				//입력된 값을 tree에 저장
			int num=scann.nextInt();
			int left=scann.nextInt();
			int right=scann.nextInt();
			tree[num].left=left;
			tree[num].right=right;
			if(left!=-1)tree[left].parent=num;
			if(right!=-1)tree[right].parent=num;
		}
		// tree의 배열 중 parent 값의 변경이 없는 경우 root이므로 root로 지정
		for(int i=1;i<=N;i++) {
			if(tree[i].parent==-1) {
				root=i;
				break;
			}
		}
		// 번호가 left -> Node -> right로 이동하기때문에 중위순회
		inOrder(root,1);
		int level=1;
		int width=0;
		// 
		for(int i=1;i<=N;i++) {
			int temp=max[i]-min[i];
			if(width<temp) {
				level=i;
				width=temp;
			}
		}
		System.out.println(level+" "+(width+1));
	}
	
	private static void inOrder(int root, int level) {
		Node cur=tree[root];
		if(cur.left!=-1)			//왼쪽에 자식이 있다면
			inOrder(cur.left,level+1);	//중위순회이기에 왼쪽부터 탐색해야함
		min[level] = Math.min(min[level], lv);	//해당 레벨에 가장 왼쪽의 번호
		max[level] = Math.max(max[level], lv);	//해당 레벨에 가장 오른쪽의 번호
		lv++;
		if(cur.right!=-1){			//오른쪽에 자식이 있다면
			inOrder(cur.right,level+1);	//오른쪽으로 탐색
		}
	}

	public static class Node{
		int point;
		int parent;
		int left;
		int right;

		public Node(int point, int left, int right) {
			super();
			this.point = point;
			this.parent=-1;
			this.left = left;
			this.right = right;
		}
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.