49189. 가장 먼 노드

프로그래머스 49189번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨

풀이

아이디어

가장 멀리 떨어진 노드의 개수를 알려면 우선 각 노드까지의 거리를 알아야 한다. 그래서 자연스럽게 다익스트라 알고리즘을 이용해야겠다고 생각했다. 하지만 이 문제에서는 모든 간선의 가중치가 1로 동일하기 때문에 무조건 처음 도착했을 때의 경로가 최단경로가 된다. 따라서 BFS를 이용해서 최단 경로를 구해줬다.

코드

/**
  APPROACH:
  하나의 노드에서 다른 노드"들"까지의 최단경로를 구해야 하는 문제이기 때문에 다익스트라 알고리즘을 먼저 생각했었음.
  하지만 이 문제는 모든 간선의 가중치가 1로 동일하기 때문에 다익스트라를 쓰지 않고 BFS만으로도 각 노드까지의 최단거리를 구할 수 있다.
*/
function solution(n, edge) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of edge) {
    adj[a].push(b);
    adj[b].push(a);
  }

  // -1은 아직 모르는 거리를 의미함
  // NOTE : BFS에서는 첫 방문 거리가 곧 최단거리이므로 (다익스트라처럼 갱신 x) Infinity 대신 -1을 쓴다.
  const dist = Array.from({ length: n + 1 }, () => -1);

  // BFS 시작
  dist[1] = 0; // 시작 지점
  const queue = [1];
  let head = 0;
  while (head < queue.length) {
    const front = queue[head++];
    const neighbors = adj[front];
    if (neighbors.length === 0) continue;

    neighbors.forEach((neighbor) => {
      if (dist[neighbor] !== -1) return;
      // 처음 방문하는 시점이 바로 최단거리이므로 주저없이 업데이트
      // 방문 기록은 겸사겸사
      dist[neighbor] = dist[front] + 1;
      queue.push(neighbor);
    });
  }

  const maxDist = Math.max(...dist);
  const answer = dist.filter((d) => d === maxDist).length;
  return answer;
}