자바스크립트 검색 알고리즘 2 : Breadth First Search

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

Array, Hash Table, Queue, Stack, Linked List에서 Traversing하는 방법은 앞선 글들에서 정리해보았다. 그런데 Graph와 Tree에서는 Traversing을 어떻게 할 수 있을까? 이 자료구조형에서 Traversing을 하고, 원하는 값을 찾을 때 사용하는 알고리즘이 바로 Breadth First Search(BFS), Depth First Search(DFS)이다.

 

결론부터 말하자면, array는 무척 심플한 자료구조이지만 searching의 경우 O(n)을 피해갈 수가 없다. Hash Table은 O(1)이지만, 자료에 순서가 존재하지 않기 때문에 사용 용도가 제한적이다. 반면 Tree와 Graph는 searching 뿐 아니라, insert, delete에서도 다른 자료구조들보다 더 나은 performance를 보여주면서 동시에 Hash Table과 달리 Order도 존재하기 때문에 상당히 유용한 자료구조이다.

 

1. Breadth First Search(BFS)

☞ BFS 로직

 

너비 우선 탐색으로, 한 level씩 돌면서 데이터를 찾는 방식이다. 즉, 0번째 level을 좌 → 우 순서로 먼저 돌고, level 0을 다 탐색하면 level 1으로 내려가서 좌 → 우로 돌면서 탐색하는 로직이다.

BFS 작동 방식

 

BFS는 각 노드를 돌 때마다, 해당 노드에 자식 노드가 존재하는지를 추적하면서 검색해야 한다. 따라서 노드를 돌 때마다 queue에 해당 노드를 추가하고, 하나씩 제거하면서 child node가 존재하는지 확인하고 있으며, 그에 따라 추가적인 메모리 공간이 사용된다.

class Node {
  constructor(value){
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  // BFS
  BreadthFirstSearch(){
    let currentNode = this.root;
    let list = [];
    let queue = [];
    queue.push(currentNode);

    while(queue.length > 0){
      currentNode = queue.shift();
      list.push(currentNode.value);
      if(currentNode.left) {
        queue.push(currentNode.left);
      }
      if(currentNode.right) {
        queue.push(currentNode.right);
      }
    }
    return list;
  }
}

const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)

console.log('BFS', tree.BreadthFirstSearch());

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}

조금 더 설명하자면, queue는 현재 노드가 속한 level을 추적하는 용도로 사용한다. 예를 들어 위 사례에서 4와 20이 있는 level을 traversing했는데 원하는 값을 찾지 못했을 경우를 가정해보자. 이 경우 현재 queue에는 [4, 20]이 들어가 있다. 원하는 값을 찾지 못했으므로 한 단계 아래 level로 내려가야 한다.

따라서 queue의 FIFO(First In, First Out) 원칙에 따라서 가장 먼저 추가된 4를 제거하면서(queue.shift()) 동시에 4에게 child node가 존재하는지 확인한다. 그리고 존재할 경우 다시 queue에 자식 노드를 추가하는 방식으로 동작한다. 

 

BFS의 경우 만약 원본 데이터가 Binary Search Tree가 아니라 옆으로 넓은 tree, 즉 한 노드에 자식 노드가 많이 존재하는 형태의 tree일 경우 queue에 대량의 데이터가 추가되어야 하기 때문에 메모리를 많이 차지할 수 있다.

 

class Node {
  constructor(value){
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  // BFS Recursive
    BreadthFirstSearchR(queue, list) {
    if (!queue.length) {
      return list;
    }
    const currentNode = queue.shift();
    list.push(currentNode.value);
    
    if (currentNode.left) {
      queue.push(currentNode.left);
    }
    if (currentNode.right) {
      queue.push(currentNode.right);
    }
    
    return this.BreadthFirstSearchR(queue, list);
  }
}

const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)

console.log('BFS', tree.BreadthFirstSearch());

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}

이처럼 재귀 함수를 이용해서도 로직을 구현할 수 있다.