[BFS]이진트리 넓이 우선탐색

문제

https://choi95.tistory.com/110?category=854389

[DFS]이진트리 순회

이전 깊이 우선 탐색한 이진트리를 이번에는 넓이 우선탐색으로 구현해보고자 한다.

 

문제풀이

너비 우선 탐색(BFS_Breadth-First Search)

• 루트 노드(Root Node) 또는 다른 임의의 노드를 정점으로, 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 적용 예: 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶은 경우
• 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용

최단 경로 탐색 이진 트리

 

문제풀이

function solution() {
  let answer = "";
  let queue = [];
  queue.push(1);
  while(queue.length) {
    let v = queue.shift();
    answer+=v + " ";
    for(let nv of [v * 2, v * 2 + 1]) {
      if(nv > 7) continue;
      queue.push(nv);
    }
  }

  return answer;
}

console.log(solution());