BFS(너비 우선 탐색)

BFS

DFS와는 다르게 그래프의 인접노드부터 탐색하는 방식입니다. BFS는 상태트리로 이해하면 쉬운데 상태 트리란 문제의 모든 가능한 상태를 노드로 구성하여 초기 상태를 루트로 에서 최종 상태로 리프로 상태 전환을 통해 연결된 트리라고 하는데 당장 BFS를 이해하기 위해 중요한건 아니라 따로 읽어보았습니다.

[Algorithms] State Space Tree Search | 상태 공간 트리 탐색

BFS의 구현

BFS는 전체 트리의 레벨 탐색이면서 출발지점에서 도착지점까지 최단거리를 탐색하기 위해 사용합니다. 트리의 레벨 -> 거리로 생각하면 쉽습니다.

 

이러한 방식으로 탐색하기 위해 큐 자료구조를 사용하게 되며 코드는 아래와 같습니다.

이진 트리 전체 탐색하기

function solution() {
  let answer = "";
  const queue = [];
  queue.push(1);

  while (queue.length) {
    const v = queue.shift();
    answer += `${v} `;

    for (let nv of [v * 2, v * 2 + 1]) {
      if (nv > 7) break;
      queue.push(nv);
    }
    // queue.push(v * 2);
    // queue.push(v * 2 + 1);
  }
  return answer;
}