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

BFS, Breadth-First Search라고 불리는 이 너비 우선 탐색은 대표적으로 많이 사용되는 알고리즘 중하나입니다.

이 글에서는 어떤 상황에서 BFS를 사용하며, 어떤 코드에서 사용되고 있는 지 알아보도록 하겠습니다.

---

너비 우선 탐색(BFS)란 무엇일까?

너비 우선 탐색(Breadth-First Search, BFS)은 그래프와 트리에서 사용되는 탐색 알고리즘 중 하나로, 

루트 노드로부터 시작해서 인접한 노드를 먼저 방문하고, 그 다음에 인접한 노드들의 

인접한 노드들을 방문하는 식으로 레벨 순서대로 진행하는 방식입니다. 

BFS는 주로 최단 경로를 찾거나, 두 노드 간의 경로가 있는지 여부를 확인하는 데 사용됩니다.

BFS 알고리즘은 다음과 같은 순서로 수행됩니다.

1. 시작 노드를 큐(Queue)에 넣습니다.
2. 큐가 비어있지 않은 동안 다음 작업을 수행합니다.
   
   1. 큐에서 노드를 하나 빼고, 해당 노드를 방문 처리합니다.
   2. 해당 노드의 인접한 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣고, 방문 처리합니다.

BFS는 모든 노드를 방문할 때까지 큐를 이용해 레벨 순서대로 노드를 처리하기 때문에, 

최단 경로를 찾을 때 사용하기에 적합한 알고리즘이라고 할 수 있습니다. 

다만, 공간 복잡도가 높아질 수 있으며 노드의 수가 많은 경우에는 메모리 사용량이 증가할 수 있습니다.

---

BFS가 사용되는 상황은 언제일까?

너비 우선 탐색(Breadth-First Search, BFS)을 사용하는 적합한 상황은 다음과 같습니다

최단 경로 찾기

두 노드 간의 최단 경로를 찾는 문제에서 BFS를 사용할 수 있습니다.

특히, 가중치가 없는 그래프에서 모든 간선의 가중치가 동일하거나 그래프가 트리와 같은 계층적 구조를 갖는 경우에 효과적입니다.

그래프의 연결성 확인

그래프 내에서 연결된 컴포넌트를 찾거나 두 노드 간에 경로가 존재하는지 확인하는 데에 BFS를 사용할 수 있습니다.

최소 스패닝 트리 찾기

가중치가 없는 그래프에서 최소 스패닝 트리를 찾는 문제에 BFS를 사용할 수 있습니다.

레벨 순회

트리나 그래프에서 각 레벨에 있는 노드들을 순서대로 방문하고 싶을 때 BFS를 사용할 수 있습니다.

예를 들어, 이진 트리에서 레벨 순회를 수행하면 같은 레벨의 노드들이 순서대로 방문됩니다.

퍼져나가는 효과 모델링

많은 문제들이 퍼져나가는 효과를 모델링할 수 있는데, 이러한 상황에서 BFS를 사용할 수 있습니다.

예를 들어, 바이러스의 전파, 소문의 확산, 소셜 네트워크에서의 친구 추천 등의 문제들이 있습니다.

 

---

BFS 예제 코드들

1. 일반적으로 구현하는 BFS 

function bfs(graph, start) {
  let visited = new Set(); // 방문한 노드를 저장할 Set 객체 생성
  let queue = [start]; // 시작 노드를 포함한 큐 생성

  while (queue.length > 0) { // 큐에 노드가 남아있는 동안
    let currentNode = queue.shift(); // 큐에서 첫 번째 노드를 꺼냄

    if (!visited.has(currentNode)) { // 꺼낸 노드가 아직 방문하지 않았다면
      console.log(currentNode); // 노드 출력
      visited.add(currentNode); // 방문한 노드 집합에 추가

      for (let neighbor of graph[currentNode]) { // 꺼낸 노드의 이웃 노드들에 대해
        if (!visited.has(neighbor)) { // 이웃 노드가 아직 방문하지 않았다면
          queue.push(neighbor); // 큐에 이웃 노드를 추가
        }
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

bfs(graph, 'A');

 

2. 이진 트리에서 BFS 출력

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

function bfsBinaryTree(root) {
  let queue = [root]; // 시작 노드를 포함한 큐 생성

  while (queue.length > 0) { // 큐에 노드가 남아있는 동안
    let currentNode = queue.shift(); // 큐에서 첫 번째 노드를 꺼냄
    console.log(currentNode.value); // 노드의 값을 출력

    if (currentNode.left) { // 노드의 왼쪽 자식이 있다면
      queue.push(currentNode.left); // 큐에 왼쪽 자식 노드를 추가
    }

    if (currentNode.right) { // 노드의 오른쪽 자식이 있다면
      queue.push(currentNode.right); // 큐에 오른쪽 자식 노드를 추가
    }
  }
}

const rootNode = new TreeNode(1);
rootNode.left = new TreeNode(2);
rootNode.right = new TreeNode(3);
rootNode.left.left = new TreeNode(4);
rootNode.left.right = new TreeNode(5);
rootNode.right.left = new TreeNode(6);
rootNode.right.right = new TreeNode(7);

bfsBinaryTree(rootNode);

 

3. BFS를 사용하여 최단 경로를 찾기

function bfsShortestPath(graph, start, end) {
  let visited = new Set(); // 방문한 노드를 저장할 Set 객체 생성
  let queue = [[start, 0]]; // 시작 노드와 경로 길이를 포함한 큐 생성

  while (queue.length > 0) { // 큐에 노드가 남아있는 동안
    let [currentNode, distance] = queue.shift(); // 큐에서 첫 번째 노드와 경로 길이를 꺼냄

    if (currentNode === end) { // 꺼낸 노드가 목표 노드와 같다면
      return distance; // 현재까지의 경로 길이 반환
    }

    if (!visited.has(currentNode)) { // 꺼낸 노드가 아직 방문하지 않았다면
      visited.add(currentNode); // 방문한 노드 집합에 추가

      for (let neighbor of graph[currentNode]) { // 꺼낸 노드의 이웃 노드들에 대해
        if (!visited.has(neighbor)) { // 이웃 노드가 아직 방문하지 않았다면
          queue.push([neighbor, distance + 1]); // 큐에 이웃 노드와 갱신된 경로 길이를 추가
        }
      }
    }
  }

  return -1; // 목표 노드에 도달할 수 없는 경우 -1 반환
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

console.log(bfsShortestPath(graph, 'A', 'F')); // 출력: 2

---

뭔가 이상하네요. 어떤 건 클래스도 섞어서 쓰네요?

신기합니다. 프론트엔드 프로젝트를 하면서 클래스를 거의 써보지 않았던 것 같은데, 2번 이진 트리에서는 사용하는군요.

그렇다면 왜 이런 구조가 나오는 걸까요?

여기에는 클래스와 함수의 구조적인 차이점이 존재합니다. 이에 대해 적어보도록 할게요

 

JavaScript에서 클래스와 함수는 객체를 생성하고 동작을 정의하는 데 사용됩니다. 

클래스와 함수의 주요 차이점은 생성자 함수와 this 키워드를 다루는 방식, 그리고 프로토타입 기반 상속과 관련된 차이라고 보면 됩니다.

 

클래스(Class)

• ECMAScript 2015 (ES6)에 도입된 새로운 문법입니다.
• 객체 지향 프로그래밍 패러다임을 지원하며, 클래스, 생성자, 상속 등의 개념을 사용합니다.
• class 키워드를 사용해 클래스를 정의하고, constructor를 사용해 생성자 함수를 정의합니다.
• extends 키워드를 사용해 다른 클래스를 상속받을 수 있습니다.
• 클래스 내부의 메서드는 암묵적으로 strict mode로 실행됩니다.

 

예시

class Animal {
  constructor(name) {
    this.name = name;
  }

  speak() {
    console.log(`${this.name} makes a noise.`);
  }
}

class Dog extends Animal {
  speak() {
    console.log(`${this.name} barks.`);
  }
}

const dog = new Dog('Max');
dog.speak(); // 출력: Max barks.

 

함수(Function)

• JavaScript에서 오랫동안 사용되어 온 방식으로, 객체를 생성하고 동작을 정의하는 데 사용됩니다.
• 일반적으로 함수 선언이나 함수 표현식을 사용해 함수를 정의합니다.
• 생성자 함수를 정의할 때, 일반적으로 첫 글자를 대문자로 작성합니다. 
• this 키워드를 사용해 객체의 속성을 정의합니다.
• 프로토타입 기반 상속을 사용하며, prototype 속성을 사용해 상속을 구현합니다.

예시

function Animal(name) {
  this.name = name;
}

Animal.prototype.speak = function() {
  console.log(`${this.name} makes a noise.`);
};

function Dog(name) {
  Animal.call(this, name);
}

Dog.prototype = Object.create(Animal.prototype);
Dog.prototype.constructor = Dog;
Dog.prototype.speak = function() {
  console.log(`${this.name} barks.`);
};

const dog = new Dog('Max');
dog.speak(); // 출력: Max barks.

 

결론적으로, 클래스와 함수 모두 객체를 생성하고 동작을 정의하는 데 사용되지만, 클래스는 보다 명시적이고 간결한 문법을 제공하며 객체 지향 패러다임을 지원합니다. 

함수는 전통적인 프로토타입 기반 상속 방식을 사용하며, 클래스보다 더 유연한 사용이 가능할 수 있습니다.

사용할 방식은 개발자의 취향과 프로젝트의 요구 사항에 따라 결정됩니다.

---

End