[알고리즘 / 백준] 2250 - 트리의 높이와 너비

www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

문제는 위와 같으며, 중위순회를 사용하면 위치가 앞인 노드부터 차례로 방문할 수 있습니다. 이때 해당 노드의 레벨을 키로 하고 노드의 위치를 값으로 하여 각 레벨에 존재하는 노드의 위치를 리스트로 저장합니다. (예: {level: [position, position, ...]. level: [position, ...], ...} )

그런 다음 각 레벨의 노드 위치 리스트에서 가장 뒤에 있는 노드의 위치 - 가장 앞에 있는 노드의 위치 + 1 한 값이 최대인 경우 해당 레벨과 너비를 저장하고 이를 출력하면 됩니다.

 

여기서 특히 주의해야 할 것은 시작노드의 숫자가 반드시 1이 아니라는 것입니다. (그런 조건이 쓰여있지 않음...ㅠ)

 

파이썬 코드는 다음과 같습니다.

# 중위 순회를 통한 너비 구하기
from sys import stdin


# 하나의 노드를 클래스로 구성
class Node:
    def __init__(self, number, parent, left_node, right_node):
        self.parent = parent
        self.number = number
        self.left_node = left_node
        self.right_node = right_node


# 중위 순회
def in_order_tree(node, level):
    global position
    if node.left_node != -1:
        in_order_tree(tree[node.left_node], level + 1)  # 왼쪽 노드가 있는 경우 먼저 방문, 레벨 + 1

    position += 1  # 해당 노드의 위치 지정
    if level in result:
        result[level].append(position)  # 해당 레벨에 이미 다른 노드의 위치가 들어가 있는 경우 리스트 뒤에 추가
    else:
        result[level] = [position]  # 해당 레벨에 노드가 처음인 경우 리스트 형태로 노드 위치 추가

    if node.right_node != -1:
        in_order_tree(tree[node.right_node], level + 1)  # 오른쪽 노드가 있는 경우 방문, 레벨 + 1


n = int(stdin.readline())  # 노드의 총 개수 입력 받기
tree = dict()

# 노드 초기화 하기 (일단 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 모두 -1 로 지정)
for i in range(1, n + 1):
    tree[i] = Node(i, -1, -1, -1)

# 각 노드 입력 받기
for _ in range(n):
    nd, left, right = map(int, stdin.readline().split())
    
    # 왼쪽 자식 노드가 있는 경우
    if left != -1:
        tree[nd].left_node = left  # 해당 노드의 왼쪽 자식 노드 추가
        tree[left].parent = nd     # 왼쪽 자식 노드의 부모 노드로 해당 노드 추가

	# 오른쪽 자식 노드가 있는 경우
    if right != -1:
        tree[nd].right_node = right  # 해당 노드의 오른쪽 자식 노드 추가
        tree[right].parent = nd      # 오른쪽 자식 노드의 부모 노드로 해당 노드 추가

position = 0  # 현재 방문한 노드의 위치
result = dict() # 레벨 별 노드의 위치를 담은 dicionary

# 부모 노드가 -1 인 노드 찾기 (해당 노드가 시작점이 됨)
root = 1
for i in range(1, len(tree) + 1):
    if tree[i].parent == -1:
        root = tree[i].number

in_order_tree(tree[root], 1)  # (시작 노드, 레벨) 전달

width = (0, 0)
for i in range(1, len(result) + 1):
    w = result[i][-1] - result[i][0] + 1
    if w > width[1]:
        width = (i, w)

print(width[0], width[1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int position = 0;
    static Map<Integer, Node> tree = new HashMap<>();
    static Map<Integer, ArrayList<Integer>> result = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i < n + 1; i++) {
            tree.put(i, new Node(-1, i, -1, -1));
        }

        for (int i = 0; i < n; i++) {
            int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (inputs[1] != -1) {
                tree.get(inputs[0]).left = inputs[1];
                tree.get(inputs[1]).parent = inputs[0];
            }

            if (inputs[2] != -1) {
                tree.get(inputs[0]).right = inputs[2];
                tree.get(inputs[2]).parent = inputs[0];
            }
        }

        int root = 0;
        for (int i = 1; i < tree.size() + 1; i++) {
            if (tree.get(i).parent  == -1) {
                root = i;
            }
        }

        inOrderNode(tree.get(root), 1);

        int[] maxWidth = {0, 0};
        for (int i = 1; i < result.size() + 1; i++) {
            ArrayList<Integer> pos = result.get(i);
            if (pos.get(pos.size() - 1) - pos.get(0) + 1 > maxWidth[1]) {
                maxWidth[0] = i;
                maxWidth[1] = pos.get(pos.size() - 1) - pos.get(0) + 1;
            }
        }

        System.out.println(maxWidth[0] + " " + maxWidth[1]);
    }

    private static void inOrderNode(Node node, int level) {
        if (node.left != -1) {
            inOrderNode(tree.get(node.left), level + 1);
        }

        position += 1;
        if (result.containsKey(level)) {
            result.get(level).add(position);
        } else {
            result.put(level, new ArrayList<>(Arrays.asList(position)));
        }

        if (node.right != -1) {
            inOrderNode(tree.get(node.right), level + 1);
        }
    }
}

class Node {
    int parent;
    int number;
    int left;
    int right;

    Node(int parent, int number, int left, int right) {
        this.parent = parent;
        this.number = number;
        this.left = left;
        this.right = right;
    }
}

 

이 문제는 중위 순회를 적용하여 앞에서 부터 차례대로 노드를 방문한다는 점을 기억하면 쉽게 풀 수 있고 주의할 점은 시작 지점의 숫자가 1이 아니라는 것입니다.