[알고리즘]너비 우선 탐색(BFS, Breadth-First Search)

✅ 트리 순회(Tree Trabersal)란?

트리 순회는

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이진트리뿐만 아니라 모든 트리에서도 일반화될 수 있다. 트리를 순회하는 데는 두 가지 전략이 존재한다. 

• 너비 우선 탐색(BFS, Breadth-first Search)
• 깊이 우선 탐색(DFS, Depth-first Search)

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

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 

👍 BFS 특징

• 두 노드 사이의 최단 경로를 탐색할 때 활용하기 좋은 방식. 멀리 떨어진 노드는 나중에 탐색하기 때문이다.
• 큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다. 

🔥 의사코드

• 큐를 만들고 방문한 노드의 값을 저장할 변수를 만든다.
• root를 가지고 큐에 넣은 다음, 큐에 무언가가 있다면 계속 루프를 돌린다. 
  • 큐에서 노드를 dequeue를 하고, 노드를 저장하는 변수에 값을 푸시한다. 
  • 제거된 노드에 left 속성이 있는 경우 큐에 추가한다.
  • 제거된 노드에 right 속성이 있는 경우 큐에 추가한다.
• 모든 값을 저장한 변수를 반환한다.

원리를 간단하게 그림으로 살펴보자. 아래와 같은 트리가 있다.

추적하고 있는 큐와 visited라는 것이 있는데 가장 마지막에 데이터의 목록, 즉 배열을 출력하게 된다. 

10을 큐에 추가하고, 루프를 돈다. 큐에 무언가가 들어있나 확인을 하고, 무언가가 있으니 꺼내서 visited 목록에 넣어준 다음. 왼쪽 값이 있나 확인한다. 있으니 그 값을 큐에 넣어주고 오른쪽을 확인한다. 

큐에서 가장 먼저 온 값(6)을 제거하고, 왼쪽과 오른쪽을 확인하고 있다면, 큐에 넣어준다. 6에서 할 작업은 끝났고

15를 큐에서 제거하고 왼쪽과 오른쪽을 살핀다. 

위와 같은 작업을 반복한다.

큐가 비었으니 작업이 종료되었다는 것을 알 수 있다. 이것이 너비 우선 탐색이다.

구현

BFS() {
    let data = [];
    let queue = [];
    let node = this.root;
    queue.push(node);
        
    while (queue.length) {
        node = queue.shift();
        data.push(node.value);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
    return data;
}