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

문제

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

분석

아래와 같은 규칙에 따라 이진트리가 그려질 때 너비가 가장 넓은 레벨과 그 너비를 구하는 문제이다.

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

문제의 열 번호를 관찰하면 중위순회의 방문순서가 곧 x좌표가 됨을 알 수 있다.
각 노드 별로 왼쪽, 오른쪽 자식을 저장할 child 배열과 각 레벨 별로 최소 x, 최대 x를 저장할 mn, mx 배열이 필요하다.
주의할 점이 root가 주어지지 않았으므로, parent를 따로 체크하여 부모가 없는 노드를 찾아내어야 한다.
그 후 중위순회를 진행하면서 레벨 별로 최소 x, 최대 x를 기록한다.

시간 복잡도는 최대 N을 넘은 반복이 없었기 때문에 O(N)이 된다.

코드

해결언어 : Java

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

public class Main {
	static int N, root, mxLevel, order = 1;
	static int[][] child;
	static int[] parent, mn, mx;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		parent = new int[N + 1];
		mn = new int[N + 1];
		mx = new int[N + 1];
		child = new int[N + 1][2];
		Arrays.fill(mn, Integer.MAX_VALUE);
		Arrays.fill(mx, Integer.MIN_VALUE);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int node = Integer.parseInt(st.nextToken());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			child[node] = new int[] { left, right };
			if (left != -1)
				parent[left] = node;
			if (right != -1)
				parent[right] = node;
		}
		for (int i = 1; i <= N; i++) {
			if (parent[i] == 0) {
				root = i;
				break;
			}
		}
		inorder(root, 1);
		int ansLevel = 1, mxWidth = 0;
		for (int i = 1; i <= mxLevel; i++) {
			int w = mx[i] - mn[i] + 1;
			if (w > mxWidth) {
				mxWidth = w;
				ansLevel = i;
			}
		}
		System.out.println(ansLevel + " " + mxWidth);
		br.close();
	}

	static void inorder(int node, int level) {
		if (node == -1)
			return;
		mxLevel = Math.max(mxLevel, level);
		inorder(child[node][0], level + 1);
		mn[level] = Math.min(mn[level], order);
		mx[level] = Math.max(mx[level], order);
		order += 1;
		inorder(child[node][1], level + 1);
	}

}