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

📝 [Lv3 가장 먼 노드]

입력

노드의 개수 n
간선에 대한 정보가 담긴 2차원 배열 vertex

제한

노드의 개수 n은 2 이상 20,000 이하
간선은 양방향, 총 1개 이상 50,000개 이하의 간선
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미

출력

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 return

풀이

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

  for(const [src, dest] of edge){
    graph[src].push(dest);
    graph[dest].push(src);
  }

  // 각 정점의 배열
  const distance = Array(n + 1).fill(0);
  distance[1] = 1;

  // BFS
  const queue = [1];
  while(queue.length > 0){
    // shift는 O(n)이지만, 요소가 적을 경우에는 자바스크립트 엔진에서 최적화를 해준다.
    // 즉, 요소 적을 경우 -> shift , 요소가 클 경우 -> 직접 구현
    const src = queue.shift(); 
    for(const dest of graph[src]){
      if(distance[dest] === 0){
        queue.push(dest);
        distance[dest] = distance[src] + 1;
      }
    }
  }
  const max = Math.max(...distance);
  return distance.filter(e => e === max).length;
}

설명

핵심 키워드 : 노드 , 간선, 최단 경로
최단 경로가 제일 큰 경우의 집합을 구하는 문제

1. 인접 리스트 생성 후, push
2. 최단거리를 알기 위한 distance 생성 및 최초값 선언
3. BFS를 활용하여 거리 초기화