BFS

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

과정

1. 1번 노드가 queue에 들어간다.

2. 1번 노드가 queue에서 나온 후 1번 노드와 연결 된 2, 3 노드들이 queue에 들어간다.

3. 2번 노드가 queue에서 나온 후 2번 노드와 연결 된 4, 5 노드가 queue에 들어간다.

4. 3번 노드가 queue에서 나온 후 3번 노드와 연결 된 6, 7 노드가 queue에 들어간다.

5. 4번 노드가 queue에서 나오지만 4와 연결된 노드가 없으므로 다음 노드로 넘어간다.

6. 나머지 5, 6, 7 노드도 5의 과정을 거치고 queue의 길이가 0이면 종료 되고, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7의 순서가 된다.

코드 구현

function solution() {
  let answer = "";
  let queue = [];
  queue.push(1);
  // queue의 길이가 0일 때 까지 반복
  while (queue.length) {
    // queue에서 가장 가까운 노드 하나 꺼낸다.
    let v = queue.shift();
    // answer에 v 추가
    answer += v + " ";
    for (let nv of [v * 2, v * 2 + 1]) {
      // 만약 nv가 7이 넘어간다면 continue
      if (nv > 7) continue;
      // v와 연결된 노드를 queue에 추가
      queue.push(nv);
    }
  }
  // queue에서 나온 순서인 answer 리턴
  return answer;
}

console.log(solution());

BFS 활용

주로 최단 거리를 구하는 경우 많이 사용