BOJ 2250 - 트리의 높이와 너비 링크
(2023.10.24 기준 G2)
문제
이진트리의 각 노드마다 행과 열 번호를 다음과 같은 규칙에 따라 정하려고 한다.
- 같은 레벨(level)에 있는 노드는 같은 행에 위치
- 한 열에는 한 노드만 존재
- 왼쪽 부트리에 있는 노드들은 왼쪽에, 오른쪽 부트리에 있는 노드들은 오른쪽에 위치.
- 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 비어있는 열은 없다.
각 레벨의 너비는 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다.
너비가 가장 넓은 레벨과 그 레벨의 너비 출력
알고리즘
중위 순회 및 트리의 성질을 이용한 루트 찾기
풀이
규칙을 요약하면 각 노드는 고유의 열 번호를 가지고 있으며, 노드가 배치된 구간 내 노드가 없는 빈 열은 없고, 왼쪽 자식 -> 자기 자신 -> 오른쪽 자식 순으로 열 번호가 1번부터 차례대로 할당된다.
열 번호가 할당되는 순서를 보면 중위 순회(inorder)의 방문 순서이다.
inorder(node) // 중위 순회 inorder(node.left) print node.value inorder(node.right)중위 순회를 시작하여 방문 순서에 따라 열 번호를 할당하는데, 우리가 구해야 하는 것은 각 레벨의 너비(max 열 번호 - min 열 번호 + 1)이므로 레벨(깊이)에 따른 열 번호의 최소, 최대를 기록하자.
중위 순회가 끝난다면, 모든 레벨의 너비를 계산하여 알맞은 답을 출력하면 된다.
그런데 말이다.. 이 문제의 생각치 못한 문제가 있다. 바로, 루트.
루트가 1이라는 말이 없다. 루트를 1로 잡아서 제출하면 WA.트리의 성질 중 하나는, 루트를 제외한 모든 노드의 진입 차수는 1이다. 물론, 모든 간선은 양방향이 아닌 부모->자식 단방향 간선으로 생각해야 한다.
그러므로 처음에 주어지는 양쪽 자식 번호가 주어질 때, 진입 차수도 같이 계산하자. 그리고 진입 차수가 0인 노드가 곧 루트가 된다.
코드
- C++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10001;
int L[MAXN], R[MAXN], ind[MAXN], mn[MAXN], mx[MAXN], p;
void dfs(int i, int lv){
// 왼쪽 자식
if (~L[i]) dfs(L[i], lv + 1);
// 현재 노드에 열 번호를 할당하게 된다.
// 현재 레벨의 최소, 최대 열 번호 갱신
mn[lv] = min(mn[lv], p);
mx[lv] = max(mx[lv], p++);
// 오른쪽 자식
if (~R[i]) dfs(R[i], lv + 1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
fill(L + 1, L + N + 1, 0); // 왼쪽 자식
fill(R + 1, R + N + 1, 0); // 오른쪽 자식
fill(ind + 1, ind + N + 1, 0); // 진입 차수
for (int _ = N, i, l, r; _; _--){
cin >> i >> l >> r;
L[i] = l; R[i] = r;
if (~l) ind[l]++;
if (~r) ind[r]++;
}
// 트리에서 루트를 제외한 모든 노드는 진입 차수가 1이다.
int root;
for (int i = 1; i <= N; i++) if (!ind[i]){
root = i;
break;
}
fill(mn + 1, mn + N + 1, N + 1); // 레벨 당 최소 열 번호
fill(mx + 1, mx + N + 1, 0); // 레벨 당 최대 열 번호
p = 1; // 할당할 열 번호
dfs(root, 1);
int result[2] = {0, 0}; // 레벨, 너비
for (int i = 1; i <= N; i++){
if (!mx[i]) break; // 레벨의 최대 열 번호가 갱신되지 않았다면 break
if (result[1] < mx[i] - mn[i] + 1){
result[0] = i;
result[1] = mx[i] - mn[i] + 1;
}
}
cout << result[0] << ' ' << result[1];
}- Python
import sys; input = sys.stdin.readline
sys.setrecursionlimit(10000)
# 중위 순회
def dfs(i, lv):
global p
# 왼쪽 자식
if ~L[i]:
dfs(L[i], lv + 1)
# 현재 노드에 열 번호를 할당하게 된다.
# 현재 레벨의 최소, 최대 열 번호 갱신
mn[lv] = min(mn[lv], p)
mx[lv] = max(mx[lv], p)
p += 1
# 오른쪽 자식
if ~R[i]:
dfs(R[i], lv + 1)
N = int(input())
L = [0] * (N + 1) # 왼쪽 자식
R = [0] * (N + 1) # 오른쪽 자식
ind = [0] * (N + 1) # 진입 차수
for _ in range(N):
i, l, r = map(int, input().split())
L[i] = l; R[i] = r
if ~l: ind[l] += 1
if ~r: ind[r] += 1
# 트리에서 루트를 제외한 모든 노드는 진입 차수가 1이다.
for i in range(1, N + 1):
if not ind[i]:
root = i
break
mn = [N + 1] * (N + 1) # 레벨 당 최소 열 번호
mx = [0] * (N + 1) # 레벨 당 최대 열 번호
p = 1 # 할당할 열 번호
dfs(root, 1)
result = [0, 0] # 레벨, 너비
for i in range(1, N + 1):
if not mx[i]: # 레벨의 최대 열 번호가 갱신되지 않았다면 break
break
if result[1] < mx[i] - mn[i] + 1:
result[0] = i
result[1] = mx[i] - mn[i] + 1
print(*result)