[Javascript/자바스크립트] (프로그래머스) 가장 먼 노드

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

코드

function solution(n, edge) {
  // 그래프 구성
  const graph = Array.from(new Array(n + 1), () => new Array());
  for (const e of edge) {
    graph[e[0]].push(e[1]);
    graph[e[1]].push(e[0]);
  }

  // BFS
  let farthest_dist = 0;
  let farthest_nodes = new Set();
  const q = [[1, 0]];
  const visited = new Array(n + 1).fill(false);
  visited[1] = true;
  while (q.length > 0) {
    const [node, dist] = q.shift();

    if (dist > farthest_dist) {
      farthest_dist = dist;
      farthest_nodes = new Set([node]);
    } else if (dist === farthest_dist) {
      farthest_nodes.add(node);
    }

    for (const nx of graph[node]) {
      if (!visited[nx]) {
        q.push([nx, dist + 1]);
        visited[nx] = true;
      }
    }
  }

  return farthest_nodes.size;
}

 

1. `solution`의 인자로 주어진 edge를 갖고 인접리스트 `graph`를 만든다. `graph[i]`에는 i와 인접한 노드들의 배열이 저장된다.

2. BFS로 모든 노드를 탐색한다. 이때 방문한 노드가 가장 거리가 먼 노드인지 확인하여 다음과 같이 처리해준다.

if (dist > farthest_dist) {
  farthest_dist = dist;
  farthest_nodes = new Set([node]);
} else if (dist === farthest_dist) {
  farthest_nodes.add(node);
}

  현재 저장된 가장 먼 거리(`farthest_dist`)보다 더 멀다면 `farthest_dist`의 값을 갱신해주고, `farthest_node`도 현재 노드만을 넣은 새로운 집합으로 갱신한다. `farthest_dist`와 같다면 `farthest_node`에 현재 노드를 추가해준다.

3. BFS로 1번 노드에서 갈 수 있는 노드들에 대해 다 탐색한 뒤에 저장된 `farthest_node`의 사이즈가 곧 1번 노드에서 가장 먼 노드들의 개수이다.