너비 우선 탐색 알고리즘 (BFS Algorithm)

DFS(Depth-First Search) 알고리즘에 이어 BFS(Breadth-First Search)를 정리해본다

---

BFS(Breadth-First Search)

탐색 알고리즘 중 하나인 BFS는 트리의 root 노드(그래프일 경우 임의의 노드)부터 시작해 모든 이웃 노드를 탐색한 뒤 아래 depth로 내려가 탐색을 반복하는 방식이다. 즉 시작 노드에서 가장 가까운 노드들을 모두 탐색하고, 그다음으로 가까운 노드들을 모두 탐색하는 것.

출처: https://en.wikipedia.org/wiki/Breadth-first_search

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

코딩테스트 연습 - 단어 변환

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)의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.

 

 

 

---

참고 자료

• https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
• https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html