너비 우선 탐색 / BFS

BFS(Breadth First Search)

BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점을 방문한 후, 인접한 정점들을 우선 방문하는 방법이다.

해당 그래프의 방문 순서가 저럴 경우, 큐에 값이 들어가고 나가는 순서는 다음과 같다.

push(0) -> pop(0) -> push(1), push(2) -> pop(1) -> push(3) -> pop(2) -> push(4) -> pop(3) -> pop(4)

BFS구현 이론

BFS 구현을 위해서는 큐를 사용해야 한다. 쉬운 이해를 위해 빨간색,파란색이 섞여있는 2차원 배열에서 파란색 칸만을 탐색하는 알고리즘을 작성하는 과정을 예로 들어 구현 플로우를 대강 정리해보자.

1. 시작 좌표(0,0)를 방문 표시 후, 큐에 push
2. 큐의 front값을 pop하고 해당 좌표에서 접해있는 상,하,좌,우 좌표를 확인
3. 인접 좌표 중에서 파란칸이면서 방문한 적 없는 좌표를 방문 표시 후, 큐에 push
4. 2,3번 과정을 계속 반복
5. 큐가 비면 탐색 종료.

---

BFS구현 코드

bfs 구현을 좀 더 편하게 하기위해선 pair STL을 알아두면 좋다. pair는 두 개체를 단일 개체로 처리할 수 있게끔 해준다. 즉 다른 종류의 데잉터 타입을 한번에 사용가능한 것이다. 사용을 위해선 utility 헤더파일이 필요하며, pair<자료형, 자료형> 페어명 형태로 선언하여 사용한다. make_pair(3,6)처럼 값을 넣어도 되고, 선언 시에 바로 값을 넣어도 된다. 각각의 데이터는 .first 와.second를 사용하여 접근할 수 있다.

BFS 알고리즘은 정말 중요하다. 구현 코드가 그렇게까지 복잡하지도 않고 어느정도 정형화된 코드가 존재하므로 해당 코드를 완벽히 이해하고 충분히 익숙해지는게 좋다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int board[100][100];    //1은 파란칸, 0은 빨간칸
bool vis[100][100];   //방문 여부 확인용 배열

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};     //상하좌우 표시용

int main(){
    queue<pair<int,int> >Q;
    vis[0][0]=1;  //시작점 방문 표시
    Q.push(make_pair(0,0));  //큐에 시작점 push

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();     //현위치 저장 후 큐에서 삭제
        Q.pop();
        
        for(int dir=0 ; dir<4 ; dir++ ){
            //현위치 주변 상하좌우 좌표 확인
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            //범위 밖일 경우 확인
            if(nx < 0 || nx >= 100 || ny < 0 || ny >= 100){
                continue;   //loop의 끝으로 이동
            }
            //이미 방문 했거나 빨간 칸인 경우 확인
            if(vis[nx][ny] || board[nx][ny]!=1){
                continue;
            }
            vis[nx][ny] = 1;
            Q.push(make_pair(nx,ny));   //조건에 맞는 좌표 방문 표시 후, 삽입
        }
    }
    
}

 

 

출처 : https://www.youtube.com/watch?v=ftOmGdm95XI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=10