BFS, Breadth-First Search라고 불리는 이 너비 우선 탐색은 대표적으로 많이 사용되는 알고리즘 중하나입니다.
이 글에서는 어떤 상황에서 BFS를 사용하며, 어떤 코드에서 사용되고 있는 지 알아보도록 하겠습니다.
너비 우선 탐색(BFS)란 무엇일까?
너비 우선 탐색(Breadth-First Search, BFS)은 그래프와 트리에서 사용되는 탐색 알고리즘 중 하나로,
루트 노드로부터 시작해서 인접한 노드를 먼저 방문하고, 그 다음에 인접한 노드들의
인접한 노드들을 방문하는 식으로 레벨 순서대로 진행하는 방식입니다.
BFS는 주로 최단 경로를 찾거나, 두 노드 간의 경로가 있는지 여부를 확인하는 데 사용됩니다.
BFS 알고리즘은 다음과 같은 순서로 수행됩니다.
- 시작 노드를 큐(Queue)에 넣습니다.
- 큐가 비어있지 않은 동안 다음 작업을 수행합니다.
- 큐에서 노드를 하나 빼고, 해당 노드를 방문 처리합니다.
- 해당 노드의 인접한 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣고, 방문 처리합니다.
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
'Development Study > Algorithm' 카테고리의 다른 글
| [JavaScript] 깊이 우선 탐색, DFS(Depth-First Search) (0) | 2023.05.04 |
|---|