1. BFS 설명
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이지만 그래프 자료구조를 알아야 되기 때문에 다차원 배열에서의 BFS를 예시로 설명함
1. 시작하는 지점을 방문했다는 표시를 남기고 큐에 넣음
2. 큐에 있는 front를 pop하고 pop한 원소의 상하좌우 칸을 확인
-> 파란색이면서 아직 방문하지 않은 칸이 있으면 방문했다는 표시를 남기고 큐에 넣음
3. 2번을 계속해서 실행하다가 큐가 비어(front 할 것이 없음)있다면 BFS 알고리즘 종료
BFS의 시간복잡도는 방문했다는 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 되고 칸이 N개일 때 O(N)이 된다. 다차원 배열에서 행이 R개이고 열이 C라면 이때의 시간복잡도는 O(R*C)가 된다.
2. BFS 코드 구현 방법
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
#define X first
#define Y second
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]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
// 상하좌우 네 방향을 고정
// (1,0) : 우, (0,1) : 상, (-1,0) : 좌, (0,-1) : 하
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// utility 헤더에 있는 pair STL 사용하면 두 자료형을 묶어서 사용 가능
pair<int, int> t1 = make_pair(10, 11);
pair<int, int> t2 = { 10, 11 }; // C++ 11 이상에서는 중괄호를 써서 사용가능
cout << t1.first << t2.second;
queue<pair<int, int>> Q;
vis[0][0] = 1; // 시작지점 방문 표시
Q.push({ 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;
Q.push({ nx, ny });
}
}
return 0;
}
상하좌우로 큐에 추가할 수 있는 칸이 있는지 검사할 때 x를 행으로 잡고, y를 열로 잡는다.
x를 행으로 잡았으니까 n(행의 수)보다 같거나 크면 안되고 y는 열로 잡았으니까 m(열의 수)보다 같거나 크면 안된다.
x축이 왼쪽과 오른쪽으로 이동하고 y축이 위아래로 이동한다는 좌표 개념 지식이 박혀있어서 처음에는 헷갈렸음 이러한게 매우 헷갈리므로 규칙을 정해두는게 중요함
3. 백준 1926
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
#define X first
#define Y second
// 상하좌우 네 방향을 고정
// (1,0) : 우, (0,1) : 상, (-1,0) : 좌, (0,-1) : 하
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int board[500][500];
int vis[500][500];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
//int* board = new int[n, m]; // 동적배열로 도화지 설정
//int* vis = new int[n, m]; // 방문여부(동적 배열은 초기값이 자동으로 들어가나? 아니면 초기화가 필요한가?)
//for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cin >> board[i, j];
// }
//}
//for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// vis[i, j] = 0;
// }
//}
int paintCnt = 0; // 그림개수
int maxWidth = 0; // 가장 큰 그림 넓이
queue<pair<int, int>> Q;
// 그림을 그릴 시작지점 설정 -> for문을 돌면서 최초로 방문하지 않으면서 1(색칠된)부분 찾기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (vis[i][j] == 0 && board[i][j] == 1) {
paintCnt++;
vis[i][j] = 1;
Q.push({ i, j });
int paintSize = 0;
while (!Q.empty()) {
paintSize++; // 큐가 비어있지 않았다는 뜻은 데이터가 있다는 뜻이므로 그림의 넓이를 1칸 늘려줌
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];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push({ nx, ny });
}
}
if (paintSize > maxWidth) maxWidth = paintSize;
}
}
}
cout << paintCnt << "\n";
cout << maxWidth << "\n";
return 0;
}
백준 1926 복습
#include<iostream>
#include<queue>
using namespace std;
int board[502][502]; // 도화지 정보
bool vis[502][502]; // 방문 정보
// 인접한 상하좌우 방향 체크
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n, m; // 도화지 크기
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
// 1.입력
cin >> n >> m;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
cin >> board[x][y];
}
}
// 2.로직
int paintCnt = 0;
int maxSize = 0;
queue<pair<int, int>> Q;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (board[x][y] == 1 && vis[x][y] == 0) {
vis[x][y] = 1;
Q.push({ x, y });
paintCnt++;
int paintSize = 1;
while (!Q.empty()) {
pair<int,int> cur = Q.front();
Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] == 1 || board[nx][ny] == 0) continue;
vis[nx][ny] = 1;
Q.push({ nx, ny });
paintSize++;
}
}
if (paintSize > maxSize) maxSize = paintSize;
}
}
}
cout << paintCnt << '\n';
cout << maxSize << '\n';
return 0;
}
