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

문제

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

2250번: 트리의 높이와 너비

---

풀이

다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 이진트리를 그릴 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 구하는 문제입니다.

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

각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1입니다.

---

접근

처음 트리 정보를 입력할 때 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호를 입력하기 때문에 각 노드는 부모노드의 정보를 갖고 있게 합니다. 또한 중위순회(inorder) 방식을 이용하여 각 레벨의 가장 왼쪽에 위치한 노드와 가장 오른쪽에 위치한 노드를 각각 기록하고 각각의 열의 번호에 몇 번 행에 노드가 있는지 기록하는 방식으로 문제를 해결했습니다.

---

코드

자바

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

class node {
    int data, parent;
    node left, right;

    public node(int data) {
        this.parent = -1;
        this.data = data;
    }
}

public class Main {

    static int cnt = 1, dpth = 1;
    static int[] arr, max, min;
    static node[] tree;

    public static void inorder(int data, int level) {
        if (tree[data].left != null) { // (3)
            inorder(tree[data].left.data, level + 1);
        }
        min[level] = Math.min(min[level], cnt);
        max[level] = Math.max(max[level], cnt);
        arr[cnt++] = level;
        if (tree[data].right != null) { // (4)
            inorder(tree[data].right.data, level + 1);
        }
        dpth = Math.max(dpth, level);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        max = new int[n + 1];
        min = new int[n + 1];
        tree = new node[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new node(i);
            max[i] = 0;
            min[i] = n;
        }
        for (int i = 0; i < n; i++) { // (1)
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int data = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if (left != -1) {
                tree[left].parent = data;
                tree[data].left = tree[left];
            }
            if (right != -1) {
                tree[right].parent = data;
                tree[data].right = tree[right];
            }
        }
        int root = 1;
        for (int i = 1; i <= n; i++) { // (2)
            if (tree[i].parent == -1) {
                root = i;
                break;
            }
        }
        inorder(root, 1);
        int width = 0, level = 1;
        for (int i = 2; i <= dpth; i++) { // (5)
            int diff = max[i] - min[i];
            if (diff > width) {
                width = diff;
                level = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(level).append(" ").append(width + 1);
        System.out.print(sb);
    }
}

위에서 설명한 대로 노드(node) 클래스는 해당 노드의 번호 data, 부모 노드의 번호 parent와 왼쪽 오른쪽 자식노드 left, right를 갖습니다. 1차원 node 배열 tree는 각 노드의 정보를 저장하고 있으며 int 배열 arr는 각각의 열의 번호에 몇 번 행에 노드가 있는지 기록하고 min과 max는 각 레벨의 가장 왼쪽에 위치한 노드와 가장 오른쪽에 위치한 노드를 각각 기록합니다. 배열 tree와 min, max를 초기화한 후에 다음 과정을 실행합니다.

 

(1) 각 노드의 번호와 왼쪽, 오른쪽 자식 노드를 입력합니다.

자식 노드(child)가 -1일 경우에는 아무것도 없다는 뜻이므로 left와 right가 -1이 아닐 경우에만 tree[child].parent = data, tree[data].child = tree[child]를 진행하여 자식노드와 부모노드 관계를 기록합니다.

 

(2) 각 노드를 순회하며 루트노드를 찾습니다.

(1)번 과정을 거쳤기 때문에 각각의 노드는 자신의 부모노드 정보를 기록하고 있을 것이며 만약 부모노드의 번호가 -1일 경우 해당 노드에 부모노드가 존재하지 않는다는 뜻이므로 루트노드로 지정합니다. 이후 inorder 메소드를 실행합니다.

 

inorder(data, level) 메소드에서 data는 현재 탐색중인 노드의 번호, level은 현재 탐색중인 level 위치입니다.

 

(3) tree[data].left가 null일 때 까지 왼쪽 자식노드를 탐색합니다.

재귀적으로 inorder(tree[data].left.data, level + 1)를 실행하며 tree[data].left가 null일 경우에 현재 노드는 트리에서 가장 왼쪽에 있는 노드입니다. 이 때 min[level]과 max[level]을 각각 최솟값, 최댓값으로 초기화하는데 이때 cnt와 비교합니다. cnt는 처음에 1로 초기화되어있으며 탐색을 진행할 때 마다 1씩 증가합니다. 왼쪽부터 오른쪽으로 순회하기 때문에 현재 열의 번호를 의미합니다. 따라서 arr[cnt] = level로 초기화한 후에 cnt += 1을 진행합니다.

 

(4) tree[data].right가 null일 때 까지 왼쪽 자식노드를 탐색합니다.

재귀적으로 inorder(tree[data].right.data, level + 1)를 실행하며 tree[data].right가 null일 경우에 현재 노드는 트리에서 가장 오른쪽에 있는 노드입니다. (3)번 과정을 반복하며 트리의 높이를 의미하는 dpth를 현재 level과 비교하여 가장 큰 값으로 합니다.

 

(5) for문을 이용하여 2번 level부터 dpth번 level까지 각 level의 너비를 계산합니다.

너비의 최댓값을 구하고 해당 너비를 갖는 level을 저장합니다.

 

모든 과정을 종료한 후에 StringBuilder에 각 값을 넣고 한꺼번에 출력합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
#define math_min(a, b) a < b ? a : b
int n, cnt = 1, dpth = 1, *arr, *visited, *max, *min;
typedef struct node {
	int data, parent;
	struct node* left;
	struct node* right;
} node;
node* tree[10001];
void inorder(int data, int level) {
	if (tree[data]->left != NULL) {
		inorder(tree[data]->left->data, level + 1);
	}
	max[level] = math_max(max[level], cnt);
	min[level] = math_min(min[level], cnt);
	arr[cnt++] = level;
	if (tree[data]->right != NULL) {
		inorder(tree[data]->right->data, level + 1);
	}
	dpth = math_max(dpth, level);
}
main() {
	scanf("%d", &n);
	arr = (int*)malloc(sizeof(int) * (n + 1));
	min = (int*)malloc(sizeof(int) * (n + 1));
	max = (int*)malloc(sizeof(int) * (n + 1));
	visited = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		tree[i] = (node*)malloc(sizeof(node));
		tree[i]->data = i;
		tree[i]->parent = -1;
		tree[i]->left = NULL;
		tree[i]->right = NULL;
		visited[i] = max[i] = 0;
		min[i] = n;
	}
	for (int i = 0; i < n; i++) {
		int data, left, right;
		scanf("%d %d %d", &data, &left, &right);
		if (left != -1) {
			tree[left]->parent = data;
			tree[data]->left = tree[left];
		}
		if (right != -1) {
			tree[right]->parent = data;
			tree[data]->right = tree[right];
		}
	}
	int root = 1;
	for (int i = 1; i <= n; i++) {
		if (tree[i]->parent == -1) {
			root = i;
			break;
		}
	}
	inorder(root, 1);
	int width = 0, level = 1;
	for (int i = 2; i <= dpth; i++) {
		int tmp = max[i] - min[i];
		if (tmp > width) {
			width = tmp;
			level = i;
		}
	}
	printf("%d %d", level, width + 1);
}

자바를 이용한 풀이와 동일합니다.

---

결론

처음에 DFS 혹은 BFS로 접근하려고 했습니다. 하지만 왼쪽 혹은 오른쪽 방향으로만 계속 진행하다보면 트리의 모양에 따라 각 레벨의 가장 왼쪽, 오른쪽 노드를 제대로 알 수 없을 것 같아서 중위순회(inorder) 방식을 사용해서 문제를 해결했습니다.