BFS(너비 우선 탐색)

BFS(너비 우선 탐색)

 

 정의 

 

너비 우선 탐색(Breadth-first search, BFS)은 그래프 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 자료구조 큐를 이용하여 구현.

 

설명을 돕기위한 그림

 

그림에서 보면 회색은 현재 큐에 들어가있는 정점이고 검은색은 방문완료한 정점이다.

 

 

 알고리즘 (2차원 배열기준)

 

1. 큐를 이용하여 시작점을 먼저 push .

2. 큐가 비워 질때까지 반복

3. 시작점을 중심으로 상,하,좌,우 중 탐색가능한지점을 큐에 넣어주고 탐색이 끝 날때 까지반복.

 

 코드 

 

 
void BFS() {
    queue <pair<int, int>> q;
    //시작 점을 q에 push
    q.push(make_pair(0, 0));
 
    //시작점 방문 체크
    visited[0][0] = 1;
 
    //큐가 빈 상태가 될때까지 반복
    while (!q.empty()) {
 
        int size = q.size();
 
        //cnt는 bfs의 깊이를 나타냄.
 
        cnt++;
 
        for (int i = 0; i < size; i++) {
 
            //q의 front부분을 중심으로
            pair<int, int> x = q.front();
 
            q.pop();
            int a = x.first;
            int b = x.second;
 
            //4방향을 탐색한다. 
            for (int j = 0; j < 4; j++) {
                int next_x = a + dx[i];
                int next_y = b + dy[i];
 
                //배열초과 여부 확인
                if (next_x >= 0 && next_x < 100 && next_y >= 0 && next_y < 100) {
 
                    //이동할 수있고 방문 하지 않았을경우 q에 넣는다.
                    if (map[next_x][next_y] && !visited[next_x][next_y]) {
                        q.push(make_pair(next_x, next_y));
                        visited[next_x][next_y] = 1;
 
                    }
                }
            }
        }
    }
 
}