[Algorithm] BFS(너비 우선 탐색)

BFS란?

너비 우선 탐색(Breadth First Search)는 너비를 우선으로 탐색하는 방법이다. 탐색을 시작하는 곳에서 가까운 부분부터 탐색을 한다는 의미이다.

최단 경로를 찾아주는 탐색방법이며, 큐를 사용한다.

BFS 원리

먼저, 탐색을 시작하는 부분(node)를 큐에 넣어준다.

한 번이라도 큐에 들어간 node는 방문했다는 표시를 해준다.

그 다음 아래의 과정을 반복한다.
1. 큐에 들어있는 node 하나를 꺼낸다.
2. 꺼낸 node와 연결된 node 중 방문하지 않은 node를 방문하여 차례대로 큐에 삽입한다. 방문하지 않은 node가 없다면, 스킵한다.

큐가 모두 비면, 탐색을 시작한 위치부터 가까운 순대로 탐색이 완료된다.

구현해보기

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int number = 7; // 탐색할 node의 수 
int checked[7]; // 방문 처리를 위한 배열 
vector<int> a[8]; // node의 index를 0이 아닌 1부터 처리하기 위해 number보다 1크게

void bfs(int start) {
    queue<int> q;
    q.push(start); // 탐색을 시작 할 node를 큐에 넣어준다. 
    checked[start] = true; // 방문처리 

    while(!q.empty()) { // 큐가 빌때까지 반복 
        // 큐에서 하나를 꺼내 출력 
        int x = q.front(); 
        q.pop();
        printf("%d ", x);

        // 큐에서 꺼낸 인접한 node들 차례대로 방문 
        for(int i=0; i<a[x].size();i++){
            int y = a[x][i]; // 인접한 노드

            if(!checked[y]){ // 방문한 상태라면 무시, 방문하지 않았다면 큐에 넣어줌
                q.push(y);
                checked[y] = true; // 방문처리 
            }
        }
    }
}

int main(void) {
    //push_back: vector의 끝에 요소를 추가할 때 사용 
    a[1].push_back(2);
    a[2].push_back(1);
    
    a[1].push_back(3);
    a[3].push_back(1);

    a[2].push_back(3);
    a[3].push_back(2);
    
    a[2].push_back(4);
    a[4].push_back(2);

    a[2].push_back(5);
    a[5].push_back(2);

    a[3].push_back(6);
    a[6].push_back(3);
    
    a[3].push_back(7);
    a[7].push_back(3);

    a[4].push_back(5);
    a[5].push_back(4);

    a[6].push_back(7);
    a[7].push_back(6);

    bfs(1);
    return 0;
}

BFS는 그 자체보다, 이것을 이용하여 다른 알고리즘에 적용한다

reference: https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16