[programmers] 가장 먼 노드 level3 with JavaScript

JavaScript를 이용한 programmers level3 가장 먼 노드를 풀이한 글입니다.

문제 설명

개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다.
1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.
가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때,
1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

BFS(너비 우선 탐색)을 활용한 최단거리를 이용해 문제를 해결할 수 있습니다.
visited 배열을 선언하여 어떤 정점 n을 방문할 때 1에서 n까지의 거리를 visited[n]에 기록합니다.
max라는 가장 먼 길이를 나타내는 변수를 선언해 정점을 방문할 때 그 정점에서 1까지의 거리가
현재의 max값보다 크다면 max값을 업데이트 해줍니다.
BFS가 종료된 이후 visited를 순회하면서 max visited[n]의 값이 같은 경우 가장 먼 노드의 개수를 카운트 해줍니다.

구현

function solution(n, edge) {
  let cnt = 0;
  const graph = [];
  for (let i = 0; i <= n; i++) {
    const row = [];
    graph.push(row);
  }

  edge.forEach((e) => {
    const [u, v] = e;
    graph[u].push(v);
    graph[v].push(u);
  });
  const visited = Array(n + 1).fill(-1);
  let max = 0;

  const BFS = (node, depth) => {
    const queue = [];
    let front, rear;
    front = rear = 0;

    visited[node] = depth;
    queue.push([node, depth]);
    rear++;

    while (front != rear) {
      node = queue[front][0];
      depth = queue[front][1];
      front++;

      for (let i = 0; i < graph[node].length; i++) {
        const nextNode = graph[node][i];
        if (visited[nextNode] !== -1) continue;
        visited[nextNode] = depth + 1;
        queue.push([nextNode, depth + 1]);
        rear++;
        if (depth + 1 > max) max = depth + 1;
      }
    }
  };

  BFS(1, 0);
  visited.forEach((v) => {
    if (v === max) cnt++;
  });
  return cnt;
}

https://github.com/jgjung9/algorithm-test-practice