[백준] 2250번 트리의 높이와 너비 Javascript(NodeJs)

문제링크

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

알고리즘: DFS,트리

문제 요약

주어진 이진 트리에서 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력 만약에 그러한 레벨이 두 개 이상이라면 가장 작은 레벨을 출력

풀이 요약

중위 순회의 탐색은 왼 -> 루 ->오 의 방향이기 때문에 이진 트리의 맨 왼쪽 열부터 순서대로 열 번호를 매길 수 있다.
여기서 실수할 수 있는 것은 루트 노드는 항상 1로 고정돼있지 않기 때문에 루트 노드를 먼저 찾는 것이 중요한데 루트 노드의 특성을 생각해본다면 부모 노드가 없다. 최상위 노드이기 때문에 그렇다는 것은 입력에서 루트 노드는 딱 한 번만 주어진다. 이것을 이용한다면 루트 노드를 쉽게 구할 수 있다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let tree = {};
let cut_node = new Array(N+1).fill(0);
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split(' ').map(x=>x*1);
    tree[input[0]] = [input[1],input[2]];
    for(let j=0; j<input.length; j++) {
        //count node
        if(input[j] !== -1) {
            cut_node[input[j]] += 1;
        }
    }
}

let root_node = find_root(cut_node);
let lv_tree = Array.from(Array(N+1), () => Array());//레벨별 트리
let row = 1;//열번호
DFS(root_node, 1);

let max_obj = {lv: 0, w: 0};
for(let i=1; i<lv_tree.length; i++) {
    if(lv_tree[i].length === 0) break;
    let cur_w = lv_tree[i][lv_tree[i].length-1] - lv_tree[i][0] + 1;
    if(max_obj.w < cur_w) {
        //낮은 레벨 부터 반복하기 때문에 max_obj값에는 같은 max width을 갖는 레벨중에서도 가장 낮은 레벨이 저장됨.
        max_obj = {lv: i, w: cur_w};
    }
}
console.log(`${max_obj.lv} ${max_obj.w}`);

function DFS(node, lv) {
    if(node === -1) {
        return;
    }
    //중위 순회 방법 왼-루-오
    let[ln, rn] = tree[node];
    DFS(ln, lv + 1);
    lv_tree[lv].push(row);
    row+=1;
    DFS(rn, lv + 1);
}

function find_root(arr) {
    let rn;
    for(let i=1; i<arr.length; i++) {
        if(arr[i] === 1) {
           rn = i;
           break;
        }
    }
    return rn;
}