[JavaScript/section 9] 04 - 이진트리 넓이우선탐색(BFS)

📌 04 - 이진트리 넓이우선탐색(BFS)

아래 그림과 같은 이진트리를 넓이우선탐색 하는 문제이다.

넓이우선탐색 : 1 2 3 4 5 6 7

언제 BFS를 사용하는가❓ 출발 지점에서 도착 지점까지의 최단 거리를 구할 때

 

• 노드 1이 출발 지점이므로 큐에 1을 추가한다.
• 큐가 모두 비워질 때 까지 while 문을 돌며 큐에서 shift 한 노드와 근접한 노드가 7보다 작거나 같으면 큐에 추가한다.
• 7보다 크다면 큐에 추가하지 않고 넘어간다.

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());