너비 우선 탐색 알고리즘 (BFS Algorithm)
DFS(Depth-First Search) 알고리즘에 이어 BFS(Breadth-First Search)를 정리해본다
BFS(Breadth-First Search)
탐색 알고리즘 중 하나인 BFS는 트리의 root 노드(그래프일 경우 임의의 노드)부터 시작해 모든 이웃 노드를 탐색한 뒤 아래 depth로 내려가 탐색을 반복하는 방식이다. 즉 시작 노드에서 가장 가까운 노드들을 모두 탐색하고, 그다음으로 가까운 노드들을 모두 탐색하는 것.
DFS 알고리즘과 달리 BFS 알고리즘은 재귀 함수로 구현할 수 없다. 현재 노드에서 가까운 노드들을 모두 탐색한 뒤 그다음으로 가까운 노드들을 탐색하기 위해선 queue(FIFO: First In First Out)을 이용해야 하고, 어떤 노드를 방문했는지에 대해 검사를 해야 된다. 시간 복잡도는 DFS와 동일하게 O(|V|+|E|)으로써 그래프 사이즈만큼의 선형 시간이 걸린다.
아래 문제를 통해 BFS 알고리즘을 연습해볼 수 있다. begin에서 target으로 변환하는 과정 중 가장 짧은 과정을 찾는 문제이며, 한 번에 한 개의 알파벳만 바꿀 수 있고 배열 words에 있는 단어로만 변환할 수 있다.
https://programmers.co.kr/learn/courses/30/lessons/43163?language=javascript
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
2022.09.25 다시 풀어봄
function solution(begin, target, words) {
let answer = 0;
if (!words.includes(target)) {
return answer;
};
let queue = [[begin, words, 0]];
while(queue.length) {
let [pNode, remain, cnt] = queue.shift();
if (pNode === target) {
answer = cnt;
break;
};
for (let i = 0; i < remain.length; i++) {
let cNode = remain[i];
let diff = cNode.split('').filter((s, j) => s !== pNode[j]);
if (diff.length === 1) {
remain.splice(i, 1);
queue.push([cNode, remain, cnt + 1]);
};
};
};
return answer;
};
function solution(begin, target, words) {
let queue = [], depth = [];
// 두 단어간 다른 알파벳이 몇 개인지 반환해주는 함수
const checkDiff = (b, w) => {
let diff = 0;
for(let i = 0; i < b.length; i++){
if(b[i] !== w[i]) diff++;
}
return diff;
}
// 두 배열 사이에 겹치는 단어가 있는지 체크하는 함수
const checkQ = (arr1, arr2) => {
// 두 배열에 겹치는 단어가 있으면 false 반환
if(arr1.length >= arr2.length){
for(let i = 0; i < arr2.length; i++){
if(arr1.includes(arr2[i])) return false;
}
}else{
for(let i = 0; i < arr1.length; i++){
if(arr2.includes(arr1[i])) return false;
}
}
// 두 배열에 겹치는 단어가 없으면 true 반환
return true;
}
// 맨 처음에는 queue에 begin을 넣고 시작
queue.push(begin);
// queue에 요소가 들어있을 때 동안 반복
while(queue.length > 0){
// equalDepth 변수에 queue를 복제한 배열 할당
let equalDepth = [].concat(queue);
// 배열 depth가 비어있다면, 배열 depth에 첫 단어(시작 노드 개념)를 push
if(depth.length === 0){
depth.push(equalDepth);
// 아니라면 함수 checkQ를 통해
// depth의 마지막 요소와 equalDepth를 비교해 겹치는 단어가 있는지 확인
}else if(checkQ(depth[depth.length - 1], equalDepth)){
// 겹치는 단어가 없으면 새로운 depth의 단어들만 있는 것이므로 depth에 push
depth.push(equalDepth);
}
// depth에 최근 투입된 배열 중 target과 일치하는 단어가 있다면, 인덱스 반환
if(depth[depth.length - 1].includes(target)) return depth.length - 1;
// queue에 먼저 들어간 단어를 빼내어 tmp에 할당
let tmp = queue.shift();
// words 배열 처음부터 끝까지 순환하며 확인
for(let i = 0; i < words.length; i++){
// 처음 마주하는 단어이며 두 단어간 다른 알파벳의 개수가 1개라면
if(checkDiff(tmp, words[i]) === 1){
// 배열 queue에 단어를 push
queue.push(words[i]);
}
}
}
// 만약 위에서 값을 반환하지 못했다면 변경할 수 없는 경우이므로 0 반환
return 0;
}
>> BFS 알고리즘은 언제 사용해야 되고 장단점은 뭘까? <<
BFS를 사용하는 경우
- 목표 노드까지의 최단 경로를 알아내고 싶을 때 사용한다
장점
- 출발 노드에서 목표 노드까지의 최단 경로를 보장한다
- 가중치가 없는 그래프에서는 시작점에서 끝 점까지의 최단 경로를 알 수 있다
단점
- 경로가 긴 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공간이 필요하다
- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다
- 무한 그래프(infinite graph)의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.