[Algorithm] 가장 먼 노드

📋 문제

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

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

 

제한 사항

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

 

입출력 예

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

 

 

✏️ 풀이

최근에 풀었었던 프로그래머스의 부대복귀와 비슷한 문제라고 생각했다. 가장 먼 노드를 계산하기 위해 BFS를 돌렸는데 먼저 graph화 시키는 것이 필요했다. 객체에 key를 node로, value를 갈 수 있는 node로 만들어줬다. 다시 방문하는 것을 막기 위해 check 배열을 만들어주고 가장 먼 노드의 개수를 찾는 문제이기 때문에 각 노드와의 거리를 저장하는 distArr 배열, 가장 먼 거리를 저장하는 maxDist 변수를 선언하고 BFS를 돌면서 값을 저장하고 maxDist를 갱신시켰다. BFS가 끝나고 distArr 배열을 순회하면서 maxDist에 할당되어 있는 값과 비교하며 answer를 계산했다.

 

⌨️ 코드

function solution(n, edge) {
  var answer = 0;

  const graph = {};

  for (const e of edge) {
    const [start, end] = e;
    if (graph[start]) graph[start].push(end);
    else graph[start] = [end];
    if (graph[end]) graph[end].push(start);
    else graph[end] = [start];
  }

  const queue = [1];
  const distArr = new Array(n + 1).fill(0);
  const check = new Array(n + 1).fill(0);
  let dist = 1;
  let maxDist = 1;

  check[1] = 1;

  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      if (!graph[node]) continue;

      for (const nextNode of graph[node]) {
        if (check[nextNode]) continue;
        distArr[nextNode] = dist;
        maxDist = maxDist < dist ? dist : maxDist;
        check[nextNode] = 1;
        queue.push(nextNode);
      }
    }
    dist++;
  }

  for (const dist of distArr) {
    if (dist === maxDist) answer += 1;
  }

  return answer;
}