[BFS] 1에서 가장 먼 노드의 개수 구하기 (JavaScript)

문제

설명

The number of nodes n and a two-dimensional array with edges is given as a parameter.

Please write a function that returns how many nodes are farthest from node 1.

The furthest node is the node with the largest number of edges when moving to the shortest path.

매개변수

• n : number type으로 number of nodes를 나타냄 (n >= 2)
• edge : Two-Dimensional Array which Indicates the edge of each node (bidirectional)

아웃풋

number type 리턴하기

입출력 예시

let edge = [[4,1],[3,4],[1,2],[2,3],[2,5],[5,3]]
let output = test1(5,edge);
console.log(output); // --> 2

 

 

Solution

BFS와 queue를 사용하여 Edge를 따라 1부터 모든 Node 방문하기

Node에 대한 중복 방문을 막으면 최단거리를 구할 수 있음

각 Node에 대한 방문 여부와 1에서 거리를 담을 배열 isVisited와 distanceArr 선언 (인덱스 === 노드 번호)

 

function test(n, edge) {
  // 아래에서 제작한 bfs 함수 사용
  return bfs(1, n, edge)
}

// bfs 함수 제작
function bfs (start, end, array) {

  const isVisited = Array(end+1).fill(false);
  const distanceArr = Array(end+1).fill(0);
  
  // queue에 start(1번 노드)를 할당하고, 방문 기록을 true로 변경
  let queue = [start];
  isVisited[start] = true;

  while (queue.length>0) {
  
    // queue의 0번째 인덱스를 꺼내 head 변수에 할당
    // 1에서 head까지의 거리에 추가로 1을 더한 뒤 distance 변수에 할당
    let head = queue.shift()
    let distance = distanceArr[head] +1;

    for (let node of array) {
    
      // head와 edge로 연결된 노드를 아직 방문하지 않았을 경우, 해당 노드를 방문하고 거리 입력
      if (node[0] === head && !isVisited[node[1]]) {
        queue.push(node[1])
        isVisited[node[1]] = true;
        distanceArr[node[1]] = distance;
      } else if (node[1] === head && !isVisited[node[0]]) {
        queue.push(node[0])
        isVisited[node[0]] = true;
        distanceArr[node[0]] = distance;
      }
    }
  }
  
  // 1에서 거리가 최대인 노드의 개수를 리턴
  let maxDistance = Math.max(...distanceArr)
  let maxArr = distanceArr.filter(el => el === maxDistance)
  return maxArr.length
}