[백준] 1967 트리의 지름 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = +input.shift();
if (n === 1) return console.log(0);

const tree = Array.from({ length: n + 1 }, () => []);
input.map((i) => {
  const [from, to, dist] = i.trim().split(' ').map(Number);
  tree[from].push([to, dist]);
  tree[to].push([from, dist]);
});

function bfs(s) {
  const check = Array.from(n + 1, () => 0);
  const queue = [];
  queue.push([s, 0]);
  let farNode = { node: 0, dist: 0 };

  while (queue.length) {
    const [node, dist] = queue.shift();
    if (check[node]) continue;
    check[node] = 1;

    if (farNode.dist < dist) farNode = { node, dist };

    for (let [nextNode, nextDist] of tree[node]) {
      queue.push([nextNode, dist + nextDist]);
    }
  }
  return farNode;
}

console.log(bfs(bfs(1).node).dist);

✔ 알고리즘 : BFS

✔ 트리의 지름 : 무작위의 점에서 가장 멀리 있는 점을 구한뒤, 그 점에서 한번 더 가장 멀리있는 점과의 거리

✔ s노드로 부터 가장 먼 노드의 정보를 return 하는 bfs함수를 작성하여 풀었다.

✔ check 배열을 통해 해당 node가 탐색이 완료된 노드인지 판단하였다.

✔ 임의로 1번 노드로부터 가장 먼 노드를 구하고 👉 bfs(1).node

✔ 그 노드에서 가장 먼 노드의 정보를 구하고 👉 bfs(bfs(1).node)

✔ 그 길이를 구하면 트리의 지름이 된다. 👉 bfs(bfs(1).node).dist

✔ 난이도 : 백준 기준 골드 4