너비 우선 탐색 ( BFS )

너비 우선 탐색 ( Breath First Search )

• 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
• 현재 노드에서 가까운 것을 먼저 탐색하는 방식
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

 

너비 우선 탐색 특징

• 재귀적으로 동작 X
• FIFO 원칙으로 탐색 ( Queue가 필요함 )
• 그래프 탐색 알고리즘은 방문한 노드를 꼭 방문 처리 해줘야 한다. ( 하지 않을 경우 무한 루프에 빠질 수 있음 )

너비 우선 탐색 장점과 단점

< 장점 >

• 출발노드에서 목표노드까지의 최단 길이 경로 보장

< 단점 >

• 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 저장 공간이 필요함
• 해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남
• 무한 그래프의 경우 해가 없는 경우 해를 찾지도 못하고 끝내지도 못하게 됨

 

너비 우선 탐색을 사용하는 경우

• 두 노드 사이의 최단경로 즉, 최단 길이를 보장해야 할 때 많이 사용된다.
   ex) 미로 찾기 같은 문제를 풀 때 많이 사용된다.

 

너비 우선 탐색 ( BFS ) 동작 방식

BFS는 다음과 같은 간단한 방식으로 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

-> 위의 1번과 2번을 계속해서 반복한다.

 

초기 상태

- 큐와 그래프를 준비

 

1. 

시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 그리고 시작 노드를 '방문 처리' 해준다. ( 방문 처리 = 빨간색 )

 

 

2.

1. 시작 노드 1을 큐에서 꺼낸다.

2. 꺼낸 노드 1의 주변 노드인 2와 3이 모두 방문된 적이 없으므로 큐에 넣어준다.

 

 

3. 

1. 큐에서 2를 꺼낸다.

2. 꺼낸 이후 2와 인접한 노드 1,3,4,5 중에서 1과 3은 이미 방문한 적이 있으므로 패스하고 
   4와 5를 큐에 삽입한다.

 

 

4. 

1. 노드 3을 큐에서 꺼낸다.

2. 꺼낸 노드 3에 인접한 노드인 1,2,6,7 중에서 1과 2는 방문한 적이 있으므로 패스하고 
   6과 7만 큐에 삽입한다.

 

  => 위와 같이 모든 노드가 방문처리가 된 후에는 남은 노드들을 큐에서 꺼내주기만 하면 된다.

 

 

최종 상태

 차례대로 큐에서 꺼내면 위와 같다. 큐에서 꺼낸 순서를 보면 1,2,3,4,5,6,7이다.
 아무렇게나 막 탐색하는 것이 아니라 1부터 시작해서 '가까운 노드'들부터 탐색이 이루어진다는 점에서
 너비 우선 탐색이라고 한다. 거리가 먼 노드인 4,5,6,7은 가장 마지막에 탐색이 이루어지게 된다.

 

BFS 구현 코드

 

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

using namespace std;

int number = 7; // 노드의 갯수
int c[7]; // 방문처리를 위한 배열 생성
vector<int> a[8]; // 이차원 배열

void bfs(int start){
  queue<int> q;
  q.push(start);
  c[start] = true;
  while(!q.empty()){
    int x = q.front(); // 큐에서 제일 앞에 값을 저장
    q.pop(); // 큐에서 제일 앞에 값을 삭제
    printf("%d ",x);
    for(int i = 0; i < a[x].size(); i++){
      int y = a[x][i];
      if(!c[y]){ // 방문하지 않았으면
        q.push(y);
        c[y] = true;
      }
    }
  }
}

int main(){
  //1과 2를 연결
  a[1].push_back(2);
  a[2].push_back(1);
  
  //1과 3을 연결
  a[1].push_back(3);
  a[3].push_back(1);

  //2와 3을 연결
  a[2].push_back(3);
  a[3].push_back(2);

  //2와 4를 연결
  a[2].push_back(4);
  a[4].push_back(2);
  
  //2와 5를 연결
  a[2].push_back(5);
  a[5].push_back(2);

  //3과 6을 연결
  a[3].push_back(6);
  a[6].push_back(3);

  //3과 7을 연결
  a[3].push_back(7);
  a[7].push_back(3);

  //4와 5를 연결
  a[4].push_back(5);
  a[5].push_back(4);

  //6과 7을 연결
  a[6].push_back(7);
  a[7].push_back(6);

  //BFS를 수행
  bfs(1);
  
}

 

결론

• BFS는 너비를 우선으로 하여 탐색한다.
• BFS를 다른 알고리즘에 적용해 응용하는 것이 핵심이다. BFS 그 자체로는 그냥 탐색 알고리즘 중 하나일 뿐
  별 의미가 없다.