백준1967 - 트리의 지름 (BFS) node.js

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

해당 문제는 트리의 지름을 구하는 문제로, 노드와 노드 사이의 가장 긴 거리를 출력하는 문제다.

 

문제 해결 방식

트리로 이루어진 문제이기 때문에 너비우선탐색 알고리즘인 BFS 알고리즘으로 최정점인 노드 1에서의 가장 거리가 먼 노드를 찾은 뒤, 그 노드로부터 가장 먼 노드 사이의 거리를 구하는 방식으로 정답을 구했다.

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

function solution(data) {
  const n = +data.shift();
  const arr = data.map((el) => el.split(" ").map(Number));

  const graph = Array.from({ length: n + 1 }, () => []);
  arr.forEach((el) => {
    const [s, e, w] = el;
    graph[s].push([w, e]);
    graph[e].push([w, s]);
  });

  function BFS(node) {
    const visited = Array.from({ length: n + 1 }, () => false);
    const distances = Array.from({ length: n + 1 }, () => 0);
    const queue = [[node, 0]];

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

      if (visited[node]) continue;
      visited[node] = true;
      distances[node] = dist;

      graph[node].forEach(([nextDist, nextNode]) => {
        const totalDist = dist + nextDist;
        queue.push([nextNode, totalDist]);
      });
    }
    const maxValue = Math.max(...distances);
    const maxIdx = distances.indexOf(maxValue);
    return [maxIdx, maxValue]; // [가장 먼 노드 번호, 가장 먼 길이]
  }

  const leaf = BFS(1);
  const result = BFS(leaf[0])[1];
  console.log(result);
}

solution(input);