백준 1926 c++ // bfs, 갯수카운팅

https://www.acmicpc.net/problem/1926

1926번: 그림

* 의사코드

큐에 넣을때마다(이동가능 일때)

cnt 변수 1씩증가 => 1의 갯수카운팅

 

* 전체코드

#include <bits/stdc++.h>
using namespace std;

int n, m, y, x, ny, nx, ret1,ret2;
int a[504][504], v[504][504];
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};


void bfs(int y, int x) {

	//cout << "bfs ; " << y << " " << x << "\n";

	int cnt = 1;
	queue<pair<int, int>> q;
	v[y][x] = 1;
	q.push({ y,x });

	while (q.size()) {
		tie(y, x) = q.front(); q.pop();
		for (int i = 0; i < 4; ++i) {
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (v[ny][nx]) continue;
			if (a[ny][nx] == 0) continue;

			q.push({ ny,nx });
			v[ny][nx] = v[y][x] + 1;
			cnt++;
			//ret2 = max(ret2, v[ny][nx]);
		}
	}

	ret2 = max(ret2, cnt);
	/*for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << v[i][j] << " ";
		}
		cout << "\n";
	}*/
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

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

	/*for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << a[i][j] << " ";
		}
		cout << "\n";
	}*/
	//queue<pair<int,int>> q;


	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (v[i][j]) continue;
			if (a[i][j] == 0) continue;
			ret1++;
			bfs(i, j);
		}
	}

	cout << ret1 << "\n" << ret2;


}