[BOJ] 2250 - 트리의 높이와 너비 (Python, JavaScript)

 

 

아이디어

 

트리를 중위 순회하여 노드들의 열 위치를 파악한 후, 각 레벨에서의 너비를 구한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

def solution():

    def inorder(u, d):
        nonlocal cnt, D
        if D <= d:
            graph.append([])
            D += 1
        left, right = children.get(u, (-1, -1))
        if left > 0:
            inorder(left, d+1)
        cnt += 1
        graph[d].append(cnt)
        if right > 0:
            inorder(right, d+1)

    N = int(input())
    children = dict()
    is_root = [1]*(N+2)
    for _ in range(N):
        num, left, right = map(int, input().split())
        is_root[left] = is_root[right] = 0
        children[num] = (left, right)
    graph = []
    cnt = D = 0
    for i in range(1, N+1):
        if is_root[i]:
            inorder(i, 0)
            break
    max_width = level = 0
    for i in range(D):
        width = graph[i][-1]-graph[i][0]+1
        if width > max_width:
            max_width = width
            level = i+1
    print(level, max_width)

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    
    function inorder(u, d) {
        if (D <= d) {
            graph.push([]);
            D += 1;
        }
        const [left, right] = children.get(u);
        if (left > 0) inorder(left, d+1);
        cnt += 1;
        graph[d].push(cnt);
        if (right > 0) inorder(right, d+1);
    }
    
    const N = Number(input[0]);
    let children = new Map();
    let isRoot = Array(N+1).fill(1);
    for (let i=1; i<=N; i++) {
        const [num, left, right] = input[i].split(' ').map(Number);
        isRoot[left] = isRoot[right] = 0;
        children.set(num, [left, right]);
    }
    let graph = [];
    let cnt = D = 0;
    for (let i=1; i<=N; i++) {
        if (isRoot[i]) {
            inorder(i, 0);
            break;
        }
    }
    let maxWidth = level = 0;
    for (let i=0; i<D; i++) {
        const width = graph[i][graph[i].length-1]-graph[i][0]+1;
        if (width > maxWidth) {
            maxWidth = width;
            level = i+1;
        }
    }
    console.log(level, maxWidth);
}

solution();