[백준] 1926 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

DFS를 이용해 그림의 최대 넓이를 구하고 벡터에 넣습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, M, mp[502][502], v[502][502], cnt;
vi d;
int dfs(int y, int x) {
	int sum = 1;
	v[y][x] = 1;
	rep(i, 4) {
		int ny = y + dy[i], nx = x + dx[i];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M && mp[ny][nx] && !v[ny][nx]) {
			sum+=dfs(ny, nx);
		}
	}
	return sum;
}
int main() {
	FAST;
	cin >> N >> M;
	rep(i, N)
		rep(j, M)cin >> mp[i][j];

	rep(i, N) rep(j, M)
		if (mp[i][j] && !v[i][j]) {
			cnt = 0;
			d.push_back(dfs(i, j));
		}
	
	d.size() ? cout << d.size() << "\n" << *max_element(d.begin(), d.end()) : cout << "0\n0";
}