BFS의 기본

* 바킹독님의 영상을 보고 요약정리한 내용입니다 *

BFS : 너비우선탐색

1. 시작하는 칸에 큐를 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당칸에 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌때까지 2번을 반복

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

• BFS 기본 문제 : BOJ 1926번 그림

#include <iostream>
#include <queue>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int n, m;
int map[501][501];
int visited[501][501];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int cnt = 0;
int maxNum = 0;
int bfs(int y, int x) {
	queue<pair<int, int>> q;
	
	visited[y][x] = 1;
	q.push({ y, x });
	int area = 1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx<0 || ny<0 || ny>n || nx>m)continue;
			if (visited[ny][nx] == 1 || map[ny][nx] == 0) continue;
			visited[ny][nx] = 1;
			area++;
			q.push({ ny, nx });
		}
	}
	return area;
	
}
int main() {
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
		}
	}
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (visited[y][x] == 1) continue;
			if (map[y][x] == 0) continue;
			cnt++;
			maxNum = max(maxNum, bfs(y, x));
		}
	}
	cout << cnt << "\n";
	cout << maxNum;
	return 0;

}

• BFS 기본 문제2 : BOJ 2178번 그림

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
string str;
int map[101][101];
int n, m;
int dy[4] = {-1, 1, 0,0};
int dx[4] = { 0, 0, -1, 1 };
int dist[102][102];
queue<pair<int, int>> q;
void bfs(int y, int x) {

	q.push({ y,x });
	dist[y][x] = 0;
	while (!q.empty()) {
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = curY + dy[i];
			int nx = curX + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
			if (map[ny][nx]!=1||dist[ny][nx]>=0) continue;
			dist[ny][nx] = dist[curY][curX] + 1;
			q.push({ ny, nx });
			
		}
	}
	cout << dist[n-1][m- 1]+1;

}
int main() {
	
	cin >> n >> m;
	
	for (int y = 0; y < n; y++) {
		cin >> str;
		for (int x = 0; x < m; x++) {
			map[y][x] = str[x] - '0';
		}
	}
	//#1. 거리를 저장할 dist 칸들을 -1로 초기화
	for (int i = 0; i < n; i++) {
		fill(dist[i], dist[i] + m, -1);
	}
	bfs(0, 0);
	
	return 0;

}