BFS

BFS(Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

예시

(0,0)과 상하좌우로 이어진 모든 파란색 칸을 확인하는 과정. BFS 알고리즘은 좌표를 담을 큐가 필요하다.

 

BFS 알고리즘이 시작되면 (0,0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다.

지금 상황에서 큐의 front는 (0,0)이고 pop을 한다. 그리고 (0,0)의 상하좌우 칸이면서 아직 방문하지 않은 칸을 찾는다. (빨간색 테두리로 표시된 칸)

 

(0,1) 과 (1,0)은 모두 파란 칸이면서 방문하지 않았다. 따라서 방문했다는 표시를 남기고 큐에 넣는다.

여기까지가 (0,0) 에 대한 처리 과정이다.

 

(0,1)을 pop 한 후 (0,1)의 상하좌우 칸을 확인한다. (0,0)은 파란 칸이지만 이미 방문했고, (1,1)은 빨간 칸이다. 유일하게 (0,2)만 파란색 칸이면서 방문하지 않았으므로 방문했다는 표시를 남기고 큐에 넣는다.

계속 이런 식으로 큐의 front를 pop 하고 인접한 칸 중에서 방문하지 않은 파란색 칸에 표시를 남기고 큐에 넣어주면 된다.

정리하면,

1. 시작하면 칸을 큐에 넣고 방문했다는 표시를 남긴다.

2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입

4. 큐가 빌 때 까지 2번을 반복

모든 칸에 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N).

 

BFS의 시간복잡도를 생각해보면 방문 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 된다. 그렇기 때문에 시간복잡도는 칸이 N개일 때 O(N)이 된다. 만약 행이 R개이고 열이 C개라면 O(RC)가 될 것이다.

STL pair

pair<int,int> t1 = make_pair(10,13);
pair<int,int> t2 = {4,6};
cout << t2.first << ' ' << t2.second << '\n'; //4 6
if(t2<t1) cout << "t2 < t1"; // t2 < t1

utility 헤더에 있는 pair. 두 자료형을 묶어서 가지고 다닐 수 있다. 

pair에는 미리 대소 관계가 설정되어 있다. 알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교한다.

예시 코드

#include <bits/stdc++.h>

using namespace std;
int board[502][502] =
        {{1,1,1,0,1,0,0,0,0,0},
         {1,0,0,0,1,0,0,0,0,0},
         {1,1,1,0,1,0,0,0,0,0},
         {1,1,0,0,1,0,0,0,0,0},
         {0,1,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; //해당 칸을 방문했는지 여부를 저장
#define X first
#define Y second
int n =7, m =10; //n= 행의 수, m = 열의 수
int dx[4] = {1, 0, -1, 0}; //아래쪽, 오른쪽, 윗쪽, 왼쪽 순 
int dy[4] = {0, 1, 0, -1};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    queue<pair<int,int>> q;
    vis[0][0] = 1; //0,0을 방문했다고 명시
    q.push({0,0}); //큐에 시작점인 (0,0) 을 삽입 
    while (!q.empty()){
       pair<int,int> cur = q.front(); q.pop();
       cout << '(' << cur.X << ", " << cur.Y << ") -> ";
       for(int dir = 0; dir<4 ; dir++){ //상하좌우 칸을 살펴본다.
           int nx = cur.X+dx[dir];
           int ny = cur.Y+dy[dir];
           if(nx<0 || nx>=n || ny<0 || ny>=m) continue; //범위 밖일 경우 넘어감
           if(vis[nx][ny]||board[nx][ny]!=1) continue; //이미 방문한 칸이거나 파란 칸이 아닐 경우
           vis[nx][ny]= 1; //(nx,ny)를 방문했다고 명시 
           q.push({nx,ny});
       }
    }
    return 0;
}

범위를 먼저 체크하는 것이 중요하다. vis[-1][0]과 같은 값을 참조할 수 있어서 런타임에러가 날 수 있다. 

범위 내에 들어오는지를 먼저 확인한 후에, vis 와 board 배열값을 봐야한다.

여러 개의 시작점에서 모든 지점으로의 거리를 구할 때 : BFS 응용

BFS를 돌 때, 큐에 쌓이는 순서는 반드시 거리 순이게 된다.

 

 

 

사진 출처 : 바킹독님 블로그 https://blog.encrypted.gg/941