이진 트리 넓이 우선 탐색(BFS) 이란 // 큐(Queue)란

너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

 

• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
• Ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
• 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

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

0레벨 먼저 탐색 , 1레벨 전부 탐색 , 2레벨 전부 탐색 등 레벨 순서대로 탐색합니다

그리고 이러한 BFS를 이용하기 위해서는 큐(Queue)에 대해 알아놓아야 합니다.

 

큐(Queue)란?

큐의 구조는 스택과 다르게 '선입선출'의 구조를 가지고 있습니다. 스택은 막힌 박스와 같아 먼저 들어온 것이 가장 나중에 나가는 구조지만, 큐는 먼저 들어온 것이 먼저 나가는 구조입니다.

 

좋은 예로 은행에 있는 번호표가 있습니다. 은행에 방문하여 기다리는데, 저보다 늦게 온 다른 분이 먼저 업무를 본다면 기분이 나쁘겠죠? 이러한 상황을 만들지 않기 위해 은행에서는 번호표를 나눠줍니다. 먼저 온 손님은 늦게 온 손님보다 먼저 서비스를 받게 하기 위해서죠. 이러한 은행의 번호표의 체계가 큐(Queue)입니다. 

 

먼저 0 레벨인 1이 큐에 들어가서 pop 되어 나와지면 1과 연결된 노드들을 전부 큐에 넣습니다. 

위의 그림에선 1과 연결된 노드의 숫자가 2와 3이기에 큐에 2,3이 들어갑니다

 

이제 1이 끝나고 레벨 1에서 2가 pop 되어 나와져서 4,5를 큐에 넣습니다.

 

이러한 로직으로 전부 하게 된다면 아래와 같은 그림이 되겠습니다.

 

 

그림으로 알아보았으니 코드를 통해 어떻게 구현해야 하는지 확인해보겠습니다.

 

function solution() {
  let answer = "";
  let queue = [];
  queue.push(1);
  while (queue.length) {
    console.log(queue);
    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());

console.log(queue)

위의 그림으로 설명한 로직과 똑같이 진행되는 것을 알 수 있습니다.