[프로그래머스] 가장 먼 노드

문제

가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

 

풀이

설명

1번 노드로부터 가장 먼 노드의 개수를 구하는 문제입니다.

 

bfs를 이용해 해결할 수 있습니다.

bfs의 특성상 가까운 거리의 노드부터 먼저 방문하게 되고, 가장 마지막에 탐색한 노드가 가장 먼 거리의 노드입니다. 전체 노드를 탐색하면서 제일 먼 거리를 갱신하고, 그 거리에서의 노드 카운트를 늘려갑니다.

 

예시 코드

function solution(n, edge) {
  const graph = Array.from({ length: n + 1 }, () => []);

  for (const [u, v] of edge) {
    graph[u].push(v);
    graph[v].push(u);
  }

  return bfs();

  function bfs() {
    const queue = new Queue();
    const dists = Array(n + 1).fill(Infinity);
    let maxDist = 0;
    let countAtMaxDist = 0;

    queue.enqueue([1, 0]);
    dists[1] = 0;

    while (!queue.isEmpty()) {
      const [node, dist] = queue.dequeue();
      if (dist > maxDist) {
        maxDist = dist;
        countAtMaxDist = 1;
      } else if (dist === maxDist) countAtMaxDist++;

      for (const nextNode of graph[node]) {
        if (dists[nextNode] !== Infinity) continue;
        dists[nextNode] = dist + 1;
        queue.enqueue([nextNode, dist + 1]);
      }
    }

    return countAtMaxDist;
  }
}