백준 1926 c++ "그림" -[PlusUltraCode]

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

1926번: 그림

[필자 사고]

이 문제는 BFS탐색 알고리즘을 이용하면 쉽게 풀 수 있다.

 

특이한 점은 1과 0의 구역을 구별하는게 핵심 포인트다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;

vector<vector<int>> Arr;
vector<vector<bool>> visited;

void Input() {
	cin >> N >> M;
	Arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
		visited[i].resize(M, false);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> Arr[i][k];
		}
	}
}
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

int BFS(int sero,int garo) {
	if (Arr[sero][garo] == 0) {
		visited[sero][garo] = true;
		return -1;
	}
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };

	queue<pair<int, int>> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	int count = 0;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		count++;
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				Arr[nextSero][nextGaro] == 1 &&
				visited[nextSero][nextGaro] == false) {
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
			}
		}
	}
	return count;
}

int main(void) {
	Input();
	int Result = 0;
	int maxCount = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (visited[i][k] == false) {
				int count = BFS(i, k);
				if (count == -1)continue;
				else {
					Result++;
					if (maxCount < count) {
						maxCount = count;
					}
				}
			}
		}
	}
	cout << Result << '\n' << maxCount;
}