[백준] 2250 트리의 높이와 너비 - JavaScript(NodeJS)

문제

2250번: 트리의 높이와 너비

 

풀이

620 - 트리 1 시리즈에서 가장 어려웠던 문제이다.

 

 

우선 문제부터 상당히 길다.

 

조건을 요약해보면

 

1. 같은 레벨의 노드는 같은 행(row)에 위치한다.
2. 한 열(column)에는 노드 하나만 존재한다.
3. 특정 노드의 왼쪽 자식은 항상 특정 노드보다 왼쪽에 위치하고, 오른쪽 자식은 항상 특정 노드보다 오른쪽에 위치한다.
4. 열(column)에는 노드가 연속적으로 존재해야 한다.(빈 열이 없어야 한다.)
5. 왼쪽/오른쪽 자식에 -1 값은 노드가 없다는 의미이다.

 

결론은
각 열마다 노드를 배치해서 트리를 표현하고, 각 행(row)에서 노드 간 거리가 최대인 거리 값과 행 번호값을 출력하면 된다.

 

※ 가장 주의해야 할 사항은 루트 노드가 1로 고정된 것이 아니므로 스스로 찾아야 한다.

 

풀이 방향

 

1. 우선 루트 노드를 찾아야 한다.

 

루트 노드를 찾기 위해선, 노드 번호와 왼쪽과 오른쪽 자식의 입력을 처리하면서 각 입력을 카운트해서
한 번만 언급이 된 노드를 찾으면 된다.

 

여기서 한 번만 언급이 된 노드는 루트노드이다. (최하단의 노드는 2번 언급된다.)

 

 

2. 문제를 잘 본 사람은 알겠지만, 이 문제는 중위 순회 문제이다.

 

알고 있다면 이 부분은 스킵하자.
그림의 1번 열부터 19번 열까지 순서대로 보면, 왼쪽자식-오른쪽자식-부모노드 순으로 위치함을 알 수 있다.
즉 이 순서대로 번호를 부여한다면 그림과 같이 각 열(column)에 노드들을 배치할 수 있다.

 

 

3. 배치가 끝나면 각 행(row, 레벨)별로 조회하면서 노드 간 거리가 최대 거리인 레벨을 찾아준다.

 

주의할 점은 거리가 가장 긴 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력해야 한다는 점인데,
레벨1부터 순차적으로 조회하면서, 최대 거리 비교시에 등호만 생략해주면 해결된다.

 

다음의 조건을 고려하여 코드를 작성해보자.

 

코드

const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const tree = Array.from({ length: N + 1 }, () => new Array()); // 트리 배열
  const findRoot = Array.from({ length: N + 1 }, () => 0); // 루트 노드를 찾는 배열
  input.map((str) => {
    const [from, ...nextInfo] = str.split(" ").map(Number);
    findRoot[from]++;
    for (let to of nextInfo) {
      tree[from].push(to);
      findRoot[to]++;
    }    // 입력을 받으면서 트리에 값을 넣어주고 findRoot 배열에서 노드 별 카운트를 증가시킨다.
  });

  const rootNode = findRoot.indexOf(1); // findRoot 배열에서 카운트가 1인 인덱스가 루트노드.
  const rows = Array.from({ length: N + 1 }, () => new Array()); 
  // 각 레벨(row)별로 노드의 column 값을 저장하기 위해 배열 rows 선언
  let column = 1; // column의 시작 값을 1로 정해준다.(문제에서 1부터 19까지 column값을 가지므로!)

  function dfs(L, node) {
    const [left, right] = tree[node];
    if (left !== -1) dfs(L + 1, left);
    rows[L].push(column++); 
    //중위 순회이므로, 이 시점에서 L(레벨) 인덱스에 column값(노드의 column값)을 넣어주고 다음 노드를 위해 column 값을 1 증가시킨다.
    if (right !== -1) dfs(L + 1, right);
  }
  dfs(1, rootNode); // Level=1, 시작 노드는 rootNode로 깊이우선탐색(dfs)을 실행


  let max = [0, 0];
  rows.map((row, level) => {
    if (!row.length) return; // 크기가 0이라면 해당 row(레벨)에는 노드가 없다.
    const width = Math.max(...row) - Math.min(...row) + 1;
    if (width > max[1]) max = [level, width]; // 해당 레벨의 최대너비 = 노드의 최대 column값 - 최소 column값 + 1
  });

  return max.join(" "); // max 변수에 [레벨, 최대너비] 순으로 값이 존재한다.
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

긴 문제 설명과 여러 조건들로 인해 조금 까다로운 문제였다.

백준에 정답으로 제출한 코드는 조금 더 더럽지만, 이해가 쉽도록 최대한 예쁘게 코드를 다듬어 보았다.

 

사실 문제를 꼼꼼히 읽지 않았어서, 루트 노드가 당연히 1이라고 생각했고 출력오류를 많이 겪었다.

 

항상 느끼지만 내가 보기엔 완벽해 보이는 코드가 계속 출력 오류를 발생시킨다면,, 내 문제일 가능성이 크다.