백준/1926/BFS/그림

백준/1926/BFS/그림
bfs관련 문제 중 기초인 그림 문제를 풀어봤습니다.
stl인 queue와 utility 헤더의 pair를 사용하였습니다.

for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1 && vis[i][j] == false) {
				//cout << "들어옴" << endl;
				Q.push({ i,j });
				vis[i][j] = true;
				count++;
                ...

count는 그림의 갯수를 세기위한 변수로 전체 배열을 돌아서 1을 찾고 방문하지 않았다면
그곳이 곧 그림의 시작점이 되는 곳이기때문에 count를 증가시킵니다.

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1 && vis[i][j] == false) {
				Q.push({ i,j });
				vis[i][j] = true;
				count++;
				size = 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] || board[nx][ny] != 1)continue;
						size++;
						vis[nx][ny] = true;
						Q.push({ nx,ny });
					}
				}
				if (max < size)
					max = size;
			}
		}

그림의 시작점을 찾았으면 그 그림을 미리 만들어둔 데이터 형태가 pair<int,int>인 queue에 시작점을 넣고 bfs를 시작합니다. bfs를 통해 size를 증가시키고 하나의 그림의 size를 얻었으면 max라는 변수와 비교하여 가장 큰 size를 찾습니다.

풀이

1. 첫번째 풀이

#include<iostream>
#include<utility>
#include<queue>
using namespace std;
int board[500][500];
bool vis[500][500];
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);
    cout.tie(0);
	int count = 0;
	int max = 0;
	int size = 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];


	queue < pair<int, int>> Q;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1 && vis[i][j] == false) {
				Q.push({ i,j });
				vis[i][j] = true;
				count++;
				size = 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] || board[nx][ny] != 1)continue;
						size++;
						vis[nx][ny] = true;
						Q.push({ nx,ny });
					}
				}
				if (max < size)
					max = size;
			}
		}

	cout << count << endl << max;;
	cout << endl;
}

2. 두번재풀이(모듈화)

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int n, m, count_num, max_area;
int count_area;
int board[500][500];
bool visited[500][500];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void solution();
void func();
void result();

void func() {
	queue<pair<int, int>>Q;
	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1 && !visited[i][j]) {
				Q.push({ i,j });
				visited[i][j] = true;
				count_num++;
				count_area = 1;
			}
			while (!Q.empty()) {
				auto 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 (visited[nx][ny] || board[nx][ny] != 1)continue;
					visited[nx][ny] = true;
					Q.push({ nx,ny });
					count_area++;
				}
			}
			result();
		}
	solution();
}

void result() {
	if (max_area < count_area)
		max_area = count_area;
}

void solution() {
	cout << count_num << '\n';
	cout << max_area;
}




int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
	cin >> n >> m;

	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}

	func();
}