[BOJ] 1926번 그림(C++)

풀이 소요시간 : 10분

전형적인 필드 카운터 문제로, 필드의 영역과 해당 크기를 저장하는 Vector 를 필요로 한다.

전체 코드(DFS)

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

int N, M;
int Cnt = 0;
int Size = 0;
int Map[501][501];
int Visit[501][501];
vector<int> Vector;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> Map[i][j];
		}
	}
}

void Dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
		if (Visit[nx][ny] == 1 || Map[nx][ny] == 0) continue;
		Size++;
		Visit[nx][ny] = 1;
		Dfs(nx, ny);
	}
}

int main() {
	Input();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Visit[i][j] == 0 && Map[i][j] == 1) {
				Visit[i][j] = 1;
				Cnt++;
				Size++;
				Dfs(i, j);
				Vector.push_back(Size);
				Size = 0;
			}
		}
	}

	if (Vector.size() == 0) {
		cout << 0 << '\n' << 0 << '\n';
	}
	else {
		sort(Vector.begin(), Vector.end());
		cout << Cnt << '\n';
		cout << Vector.back() << '\n';
	}
}