🎯 BFS

BFS(Breath First Search)는 너비 우선 탐색이라고 하며 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져있는 노드를 나중에 방문하는 탐색 방법이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는데, BFS는 그 반대다. 보통 BFS는 선입선출 방식인 큐 자료구조를 이용하는 것이 일반적이다.

다른 언어의 경우는 보통 내장 라이브러리에 큐를 제공하고 있지만 자바스크립트는 큐와 관련된 객체가 내장되어 있지 않다. 따라서 BFS를 이용하기 위해서는 큐 자료구조를 따로 구현해줘야 한다.

💎 BFS의 동작 방식

우선 탐색 시작 노드를 큐에 삽입하고 방문 처리한다. 다음으로 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 이 과정을 더 이상 수행할 수 없을 때까지 반복한다.

🎯 BFS 구현 (JS)

function BFS(graph, start, visited) {
  const queue = new Queue();
  queue.push(start);
  visited[start] = true;

  while (queue.size()) {
    const v = queue.popleft();
    console.log(v);

    for (const node of graph[v]) {
      if (!visited[node]) {
        queue.push(node);
        visited[node] = true;
      }
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(6).fill(false);
BFS(graph, 0, visited);

큐(Queue) 구현 코드

class Queue {
  constructor() {
    this.store = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    if (this.store[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.front + 1;
    }
  }

  push(value) {
    if (this.size() === 0) {
      this.store['0'] = value;
    } else {
      this.rear += 1;
      this.store[this.rear] = value;
    }
  }

  popLeft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front = 0;
      this.rear = 0;
      return temp;
    } else {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front += 1;
      return temp;
    }
  }
}

🎯 BFS의 시간 복잡도

BFS는 DFS와 마찬가지로 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n+e)이며, 인접 행렬로 펴 표현된 경우 O(n^2) 시간이 걸린다. BFS와 DFS 모두 희소 그래프를 사용할 때 인접 리스트를 사용하는 것이 효율적이다.

🎯 BFS 와 DFS 언제 사용하는 것이 좋을까?

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다. DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다. 둘 중 편한 것을 사용하면 된다.

  • 경로의 특징을 저장해둬야 하는 문제 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)

  • 최단거리 구해야 하는 문제 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.