문제
이진 트리를 규칙에 따라 2차원 격자에 배치할 때, 너비가 가장 넓은 레벨과 그 너비를 구하라. 너비가 같으면 레벨이 작은 것을 출력한다.
입력
첫째 줄에 노드 수 N (1 이상 10,000 이하), 둘째 줄부터 각 노드의 번호, 왼쪽 자식, 오른쪽 자식이 주어진다 (-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 | 3 18 |
풀이
중위 순회(inorder)로 각 노드의 열 위치를 결정하고, 레벨별 최소/최대 열을 추적한다.
- 부모 배열
p[]를 이용해 루트 노드를 찾는다 (부모가 0인 노드) - 중위 순회를 수행하며, 방문 순서를 열 번호(row)로 할당한다
- 각 레벨에서
min[level]과max[level]을 갱신한다 - 모든 레벨을 순회하며
max[i] - min[i] + 1이 가장 큰 레벨을 찾는다
핵심 아이디어: 이진 트리의 중위 순회 순서가 곧 열 배치 순서이다. 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순으로 방문하면 자연스럽게 왼쪽부터 오른쪽까지 배치된다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day319BOJ2250트리의높이와너비 {
static int ans, N, row = 1;
static int[] p, l, r, min, max;
static boolean[] visited;
static List<List<Integer>> widths;
static int ansWidth = 0;
static int ansLevel = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
p = new int[N + 1];
l = new int[N + 1];
r = new int[N + 1];
min = new int[N + 1];
Arrays.fill(min, 20000);
max = new int[N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int cur = Integer.parseInt(st.nextToken());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
if (left != -1) {
p[left] = cur;
}
l[cur] = left;
if (right != -1) {
p[right] = cur;
}
r[cur] = right;
}
int root = findRoot(1);
inorder(root, 1);
for (int i = 1; i <= N; i++) {
if (ansWidth < max[i] - min[i] + 1) {
ansWidth = max[i] - min[i] + 1;
ansLevel = i;
}
}
System.out.println(ansLevel + " " + ansWidth);
}
static int findRoot(int cur) {
if (p[cur] != 0)
return findRoot(p[cur]);
else
return cur;
}
static void inorder(int cur, int level) {
if (cur != -1) {
inorder(l[cur], level + 1);
min[level] = Math.min(min[level], row);
max[level] = Math.max(max[level], row);
row++;
inorder(r[cur], level + 1);
}
}
}복잡도
- 시간: O(N) - 중위 순회 + 레벨별 너비 계산
- 공간: O(N) - 트리 구조 및 레벨별 최소/최대 배열