[Algorithm] BFS / c++

바킹독의 실전 알고리즘 0x09강 정리

 

BFS(Breadth First Search)

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

 

순서

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

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

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

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

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

 

예시코드

#include <bits/stdc++.h>
using namespace std;
#define X first; // pair의 first, second를 쉽게 쓰기 위해 X, Y 로 정의
#define Y second;
int board[502][502] = {}; // 확인해야할 이차원 배열
bool vis[502][502]; // 방문체크할 이차원 배열
int n = 7, m = 10;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int, int>> Q; // 큐 선언
    vis[0][0] = 1; // 처음 칸 방문 표시
    Q.push({0,0}); // 큐에 (0,0) push

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop(); // 큐의 front 값 cur에 대입 후, 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; // 방문 표시
            Q.push({nx, ny}); // 큐에 좌표 push
        }
    }
}