BFS 알고리즘은 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 너비를 우선으로 방문한다는 의미는 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘인데, 시작 정점에서 거리가 가까운 정점부터 차례대로 방문한다.
BFS의 구현
BFS는 FIFO(선입선출)의 특징을 가진 큐를 이용하여 구현할 수 있다.
1. 시작 정점 설정: 탐색을 시작할 정점을 큐에 넣고, 방문 처리를 한다.
2. 탐색 시작: 큐가 비어있지 않는 동안에는 계속 탐색한다.
3. 정점 꺼내기: 큐에서 정점을 하나 꺼낸다.
4. 인접 정점 확인 및 추가: 꺼낸 정점과 연결된 모든 인접한 정점들을 확인하고, 만약 방문한 적이 없다면 큐에 추가하고 방문 처리를 한다.
-> 모든 정점이 큐에 한번씩 들어가므로, 시간복잡도는 O(N)
이를 코드로 구현해보자.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] // 그래프를 배열로 표현
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n,m // n = 행의 수, m = 열의 수
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; // (0, 0)을 방문했다고 명시
Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
while(!Q.empty()){
pair<int,int> cur = Q.front();
Q.pop();
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 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});
}
}
}시작점인 (0,0)을 큐에 넣고 방문처리를 한 후, (0,0)과 거리가 가까운 순서대로 조건에 맞는 모든 정점을 탐색한 뒤, 모든 정점을 방문처리 하여 큐에 push할 정점이 없어 큐가 비어있는 경우에 탐색을 종료한다.
사용 예시
BOJ 1926번: 그림
문제 설명
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int draw[501][501];
bool vst[501][501]; // 방문 체크
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int num = 0, area = 0, maxArea = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;
cin >> n >> m;
queue<pair<int, int>> Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> draw[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (draw[i][j] == 1 && vst[i][j] == false) { // 각 그림의 시작점 찾기
Q.push({ i,j });
vst[i][j] = true;
num++;
}
while (!Q.empty()) { // 큐가 비면 종료
pair<int, int> p = Q.front();
Q.pop();
area++;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int nx = p.first + dx[i];
int ny = p.second + dy[i];
if (nx >= n || ny >= m || nx < 0 || ny < 0) continue; // 범위를 벗어남
if (vst[nx][ny] || draw[nx][ny] == 0) continue; // 방문한 적 있거나 0이면
vst[nx][ny] = true;
Q.push({ nx,ny });
}
}
}
maxArea = max(area, maxArea);
area = 0;
}
}
cout << num << '\n' << maxArea;
}- 값이 1인, 즉 색칠된 정점을 탐색하면서 BFS 알고리즘을 적용할 시작점을 찾는다.
- 시작점을 찾았다는 것은 그림이 시작된다는 의미이고, 아래 BFS 알고리즘을 통해 시작점과 연결된 모든 정점은 방문 처리 되기 때문에 중복되지 않으므로, 그림의 개수인 num을 1 증가시킨다.
- 시작점을 찾으면 시작점을 큐에 push하고 BFS 알고리즘을 적용시켜서 시작점과 인접한 모든 정점을 탐색하고 방문처리 한다.
- 정점을 큐에서 pop할때 area값을 1 증가시켜 그림의 넓이를 계산한다.
- 큐에 push할 정점이 없을때까지 계산한 후, 그림의 넓이가 이전에 계산했던 그림의 넓이보다 큰 지 확인하는 과정을 반복해서 가장 넓은 그림의 넓이를 구한다.
