[백준] 1967 트리의 지름 - JavaScript(NodeJS)

문제

1967번: 트리의 지름

 

풀이

1991번 문제와 거의 동일한 문제이다.

1991번 문제 이전 포스팅 <- 클릭

 

그래서 이전 포스팅에서 이용한 DFS를 그대로 사용해서 문제를 해결하려고 했다.

 

이 문제도 1991번 문제와 동일하게 트리의 지름을 구하는 문제이며,
트리의 지름을 구하기 위해 dfs 혹은 bfs를 2번 적용하면 해결된다.

 

(설명이 너무 생략되었다고 생각하면, 이전 포스팅을 참고하자.)

 

사실 1991번에서 구현한 dfs를 그대로 가져와서 사용할 생각이었는데...

이유 모를 무수한 에러에 부딪혔다.(크롬 콘솔에서 테스트는 잘 되는데, 채점에서는 오답이 나온다.)

 

그래서 결국 이번에는 BFS로 구현했다.

 

풀이 방향

1991번과 풀이 방향은 동일하다.

 

임의의 노드 X에서 bfs를 실행해서 최대 거리인 노드 Y와 거리를 구하고,
최대 거리 노드 Y에서 한번 더 bfs를 실행해서 Y로부터 최대 거리 노드인 Z를 구하고, 최대 거리를 구한다.

이 Y와 Z는 서로 트리 지름의 끝 점에 해당하며 최대 거리는 지름이 되므로 출력해준다.

 

1991번에서 이용한 dfs는
함수가 재귀적으로 동작하므로 체크 배열을 함수 밖에 선언했고
두 번째 dfs 실행에서 체크 배열을 초기화하는 작업이 필요했다.

 

하지만 이 문제에서 이용할 bfs는
함수 내에서 반복문이 동작하므로, 함수 내에 체크 배열을 선언하는 편이 더 깔끔하다.

이렇게 함수 내에 체크 배열을 선언해주면 함수가 실행될 때 마다 새로 선언되므로, 신경쓰지 않아도 된다.

 

코드를 보는 편이 이해가 더 빠르겠다.

코드

const sol = (input) => {
  const N = +input[0];
  if (N === 1) return 0; // N=1 이면 지름은 0이다.
  input = input.slice(1);
  const tree = Array.from({ length: N + 1 }, () => new Array());
  input.map((str) => {
    const [from, to, dist] = str.split(" ").map(Number);
    tree[from].push([to, dist]);
    tree[to].push([from, dist]);
  }); // tree배열의 인덱스에 노드에 연결된 다른 노드와 거리 정보를 배열 쌍으로 넣어준다.
  tree.sort((a, b) => a[0] - b[0]);

  function bfs(s) {
    const check = new Array(N + 1).fill(0); // 체크 배열을 bfs함수 내에 선언해주는 것이 더 깔끔하다.
    const queue = [];
    queue.push([s, 0]);
    let max = { node: 0, dist: 0 }; // max 변수에는 최대 거리와 최대 거리인 노드 정보가 들어간다.
    while (queue.length) {
      const [node, dist] = queue.shift();
      if (check[node]) continue;
      check[node] = 1;
      if (max.dist < dist) max = { node, dist }; // 최대 거리이면, max 변수를 갱신한다.
      for (let [nextNode, nextDist] of tree[node]) {
        queue.push([nextNode, dist + nextDist]); // 다음 노드와 노드까지의 누적 거리를 큐에 넣어준다.
      }
    }
    return max; // s 노드를 시작으로 모든 노드를 방문하면 max 변수에는 최대 거리 정보가 들어있다.
  }

  return bfs(bfs(1).node).dist;
  // bfs(N)의 결과는 max 객체이므로, bfs를 2번 반복한 결과 값의 dist는 최대 거리이다.
};


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

 

다행히도 추가적인 오류 없이 제출에 성공했다.