BFS(Breadth First Search)

BFS에 대한 이해

- BFS 란, 시작점으로 부터 너비(거리)를 우선으로 탐색을 진행하는 방법이다. 

- 보통 BFS 알고리즘은 그래프 자료구조나 2,3차원의 배열과 함께 쓰인다.

 

너비를 우선으로 탐색한다함은 '거리'를 기준으로 가까운 노드부터 탐색한다는 의미이다.  다음과 같은 그래프 자료구조에서 보라색 노드를 시작 지점으로 탐색을 진행할 때, 보라색 노드로 부터 거리가 1인 초록색 노드들을 먼저 탐색하고, 보라색 노드로 부터 거리가 2인 주황색 노드들은 다음으로 탐색한다. 

 

 

따라서 BFS 탐색 방법을 사용하여 위의 그래프를 모두 탐색하는 경우, 노드 번호를 기준으로 1 -> 3 -> 2 -> 5 -> 4 -> 6 -> 7 을 지나 탐색이 종료된다.

 

 

 

BFS의 구현

BFS는 '큐'로 구현하는 것이 일반적이다.

빈 큐에 시작 노드의 번호를 넣고, 해당 노드를 방문했음을 임의의 배열(vis)에 체크해준다.

 

이후, 큐에서 먼저 저장된 순서대로 노드를 하나씩 꺼내 해당 노드와 인접한(연결된) 노드들 중, 아직 방문하지 않은 노드들을 큐에 넣어준다. 큐에 노드들을 넣을 때마다, 방문했음을 임의의 배열(vis)에 체크해주어야 한다. 

 

결과적으로, 큐에는 시작지점으로 부터 가까운 노드들 순으로 좌표(노드 번호)가 저장되었다가 빠지게 된다.

 

그래프 자료구조에 대한 BFS 코드는 다음과 같다.

 

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

using namespace std;

vector<int> graph[8] = { // x 번째 노드에 연결되어있는 노드들의 번호 graph[x]
    {}, 
    {3, 2, 5}, 
    {1, 5, 7}, 
    {1, 4, 6}, 
    {3}, 
    {1, 2}, 
    {3}, 
    {2}}; 

int vis[8]; // 해당 노드를 방문했는지 확인하는 배열

int main() {

    queue<int> q;

    q.push(1); //시작 노드를 큐에 추가
    vis[1] = 1; //시작 노드에 방문했음을 기록

    while (!q.empty()) { //큐가 빌 때까지 반복

        int cur = q.front(); //현재 노드 확인
        q.pop();
        printf("%d ", cur);

        for (int i=0; i<graph[cur].size(); i++) { 
            int next = graph[cur][i]; //cur(현재 노드)에 인접한 노드 확인
            if (vis[next])  continue; //인접한 노드 중 이미 방문한 노드는 다시 방문하지 않음
            q.push(next); //인접한 노드 중 아직 방문하지 않은 노드를 큐에 추가
            vis[next] = 1; //큐에 넣은 노드는 방문한 노드임을 표시
        }
    }
    return 0;
}

/*output: 1 3 2 5 4 6 7 */

 

 

 

배열에서의 BFS

BFS는 너비를 우선으로 탐색하기 때문에, 시작점으로 부터 각 노드들까지의 최단 거리를 구하는데 유용하게 쓰인다.

다음과 같은 배열에서 0을 지나갈 수 있는 통로, 1을 지나갈 수 없는 벽이라 할 때 [0,0]에서 [4, 4]까지의 최단 경로를 구해보자.

 

 

배열에서 BFS를 구현할 때 역시 '큐'를 사용하며, 그래프에서의 구현과 다른 점은 두가지 뿐이다.

- 인접한 좌표를 확인하기 위해 int dx[4], int dy[4] 와 같은 이동 경로 배열을 사용한다.

- 좌표의 방문 여부(혹은 시작점으로 부터의 거리)를 기록하기 위해 또 다른 배열 int dist[][]를 사용한다.

 

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
using ii = pair<int, int>;

#define X first
#define Y second

int N = 5;
int map[5][5] = { 
    {0, 0, 0, 1, 0}, 
    {0, 1, 0, 0, 0}, 
    {1, 0, 0, 1, 0}, 
    {1, 0, 0, 1, 0}, 
    {1, 1, 0, 0, 0}};

int dist[5][5]; // dist[x][y]: 출발지로 부터 (x, y)까지의 거리

int dx[4] = {-1, 1, 0, 0}; //현재좌표를 기준으로 상하좌우를 인접한(이동 가능한) 좌표라 하였을 떄,
int dy[4] = {0, 0, -1, 1}; //dx와 dy를 네번 순회하며 인접 좌표 확인 가능

int main() {

    memset(dist, -1, sizeof(dist)); //아직 방문 하지 않은 좌표의 dist[i][j] 값을 -1로 초기화

    queue<ii> q; 
    q.push({0, 0}); //시작 좌표를 큐에 추가
    dist[0][0] = 0; //시작 좌표에서 시작 좌표까지의 거리는 0

    while (!q.empty()) {

        ii cur = q.front(); //현재 좌표
        q.pop();

        for (int i=0; i<4; i++) {
            int nx = cur.X+dx[i]; //(nx, ny): 현재 좌표와 인접한 좌표 확인
            int ny = cur.Y+dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; //배열을 벗어난 좌표로는 이동 불가
            if (map[nx][ny] || dist[nx][ny] != -1) continue; //인접 좌표가 1(벽)이거나 방문한 적이 있으면 이동 불가
            
            q.push({nx, ny});
            dist[nx][ny] = dist[cur.X][cur.Y]+1; //출발지로부터 인접좌표까지의 거리는 현재좌표까지의 거리 + 1
        }
    }

    printf("%d", dist[4][4]);
    return 0;
}

/*output: 8*/

 

 

배열 및 BFS와 관련하여 많은 응용 문제들이 있다. 하지만 이들의 핵심은 모두 '큐'를 이용하여 출발지로 부터 도착지까지의 최단 거리(시간)을 구하는 것이므로, 큐에 처음으로 추가되는 시작점이 무엇인지, 각 지점으로 부터 이동 가능한 다음 배열은 어떠한 조건인지를 중점적으로 생각해보면 어렵지 않게 구현할 수 있다.