[JS Algorithm] 가장 먼 노드 (BFS)

1. 그래프탐색_BFS

• 그래프 탐색이 필요할 경우, JS에서는 DFS가 꼭 필요한 상황이 아니라면 별로 선호하지 않아서 BFS로 구현하는 것을 추천한다고 한다...!

2. 구현 과정

1. 변수 준비

const n = 6;
const edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]];

2. 연결리스트 만들기

const connects = new Array(n).fill().map(_ => []);
// n이 3일 경우, [[],[],[]] 이렇게 반환됨!

3. 양방향 그래프 선언 과정

• 서로의 좌표에 모두 연결된 노드를 넣어준다.

for (const e of edge) {
  connects[e[0]-1].push(e[1]-1);
  connects[e[1]-1].push(e[0]-1);
}

4. BFS를 통해 가장 멀리있는 노드의 개수를 체크하는 과정

• 그래프의 Depth를 추척하면서, visited 변수를 선언해 해당 변수에 방문 표시로
  자신의 depth를 넣어주는 방식으로 구현!
• 이 때 자신의 depth는 출발한 시점부터 +1 되면서 누적됨!

1) 필요한 변수

const visited = [1]; // 1. depth를 누적하기 위함
const queue = [0]; // 2. 방문해야 되는 노드들을 저장해놓은 용도
// ex) 0번째 노드와 연결된 노드들을 queue 안에 다 떄려넣음!

2) 반복문

while(queue.length) {
  const cur = queue.shilt();
  
  for (let next of connects[cur]) {
    if (!visited[next]) {
      visited[next] = visited[cur] + 1;
      queue.push(next);
    }
  }
}

5. 가장 먼 노드 구하는 방법

const max = Math.max(...visited);
const length = visited.filter(el => el === max).length;
// visited 배열에서 filter로 최댓값인 애를 찾고, 그 길이를 반한!