[Data Structure] BFS (너비 우선 탐색)

Bredth-First-Search (너비 우선 탐색)란?

BFS의 원리는 간단하게 말하면 퍼지는 물결파 이다. 잔잔한 호수에 돌을 던져 생기는 물결파를 떠올려 보자.

동그란 원형의 파원을 일으키며 퍼져나간다. 이렇게 동일한 거리의 지점들은 동시에 탐색을 하는 방법이다.

핵심은 1번의 탐색 루틴에서 하나의 level에 있는 모든 정점을 탐색한다는 것이다.

저번 DFS처럼 BFS방식을 그래프를 통해 설명해보겠다.

 

 

앞서 DFS에서 사용한 그래프와 동일한 형태의 그래프다. DFS와 마찬가지로 1번 정점부터 탐색을 시작해보자.

 

 

1번 정점을 탐색 완료했다면 현재 정점의 인접하는 정점들을 확인한다. BFS는 다음에 탐색할 위치를 인접한 모든 정점으로 선택한다. 따라서 다음 탐색은 2, 3번 정점으로 이동한다.

 

 

원리는 2, 3번 정점이 동시에 이뤄지는 것이지만 실제 탐색은 2번, 3번 순으로 탐색한다.

2번 정점을 탐색할 때, 4번과 5번 정점이 탐색하지 않은 정점들이므로 다음 탐색 정점들에 넣어준다. 이때, 탐색 정점들은 Queue에 넣어준다,

2번 정점 탐색을 완료했다면, 이제 3번 정점을 탐색한다.

3번 정점을 탐색할 때, 3번 정점에서 갈 수 있는 6번 정점을 4, 5번 정점처럼 Queue에 넣어준다.

이제 1번에 연결된 level 1의 모든 정점 탐색이 끝났다.

다음 level인 level 2의 정점들을 탐색한다.

 

 

이제 level 2의 정점들을 탐색하자. 4번부터 차례대로 탐색을 수행한다.

4번 정점을 탐색할 때, 다음 정점인 7번 정점을 Queue에 넣어준다. 그 후 5번 정점을 탐색한다. 5번 정점에서는 더 이상 탐색할 정점이 없다. 6번 정점도 마찬가지이다.

 

 

이제 마지막 level인 7번 정점을 탐색하면 BFS 탐색이 종료된다.

전체적으로 BFS를 모아서 보면 아래와 같이 탐색을 수행한다.

 

 

BFS 예시

BFS는 미로찾기에서 최단 경로 찾기에 사용할 수 있다.

 

 

앞서 DFS에서 사용한 미로를 그대로 가져와서 이번엔 다르게 탐색해보자.

 

 

동시다발적으로 미로를 채워나가는 것을 알 수 있다. 따라서 바로 목표지점일때 탐색 종료를 하면 도착점까지 최단 경로를 알 수 있다.

 

BFS implementation (BFS 구현)

이번 BFS는 바로 실전 코딩방식으로 넘어가겠다.

 

인접리스트 풀이 코드

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

vector<vector<int>> Node;
vector<bool> visit;

void bfs(int start)
{
    queue<int> Q;
    
    Q.push(start);
    visit[start] = true;
    
    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        
        cout << "Visit " << curr << " vertex\n";
        
        for (int next : Node[curr])
        {
            if (!visit[next]) {
                visit[next] = true;
                Q.push(next);
            }
        }
    }
}

int main() {
  cin >> N;
 
  // 시작 정점이 1인 경우로 설정
  map.resize(N + 1);
  visit.resize(N + 1);
 
  for (int i = 0; i < M; i++) {
    int u, v;
 
    cin >> u >> v;
 
    map[u].push_back(v);
    map[v].push_back(u);
  }
 
  bfs(1);
}

핵심은 Queue에 다음 탐색 정점을 넣으면서 한단계 level들을 동시에 순환시키는 것이다.

이때, 들어가는 순서를 좀 조작해야하는 문제들도 있으니 주의할 필요가 있다.

이미 앞서서 이론적으로 설명한 기반이 인접리스트라 코드는 동일하다. 단지 문제풀이때는 전역변수로 설정해서 모든 값이 정수는 0으로, bool타입은 false로 자동 초기화가 된다.

 

인접행렬 풀이 코드

#include <cstdio>
#include <queue>
#include <functional>
using namespace std;

typedef pair<int, int> P;
int N, M;
int map[101][101];
bool visit[101][101];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
queue<P> Q;


void BFS(int x, int y)
{
    visit[x][y] = true;
    Q.push(P(x, y));
    
    int tx, ty;
    
    while (!Q.empty()) {
        tx = Q.front().first;
        ty = Q.front().second;
        
        Q.pop();
        
        cout << "x : " tx << " , y : " << ty << " visit \n";
        
        for (int i = 0; i < 4; i++) {
            int nx = tx + dx[i];
            int ny = ty + dy[i];
            
            if (map[nx][ny] == 1 && nx < N && ny < M && !visit[nx][ny]) {
                visit[nx][ny] = true;
                Q.push(P(nx, ny));
            }
        }
    }
}

int main() {
  int u, v;
  // 시작 정점 역할
 
  cin >> N;
  // N x N 행렬로 만든다고 가정한다.
 
  // map이 입력으로 주어질 때로 가정
  for (int i = 0; i < N; i++) {
    for (int i = 0; i < N; i++) {
      int curr;
 
      cin >> curr;
      // 보통 입력은 1, 0으로 주어진다.
      map[i][j] = curr;
    }
  }
 
  cin >> u >> v;
 
  BFS(v, u);
}

전체적인 코드는 인접리스트와 비슷하다.