🖊️ 문제

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

---

🖊️ 풀이

연결요소의 개수를 세는 전형적인 문제라고 봤다.

연결요소가 끝나면, 각 연결요소내에서 탐색한 집들의 개수를 최종 결과 벡터에 넣어줬다.

그리고, 불필요한 노드 방문을 막기 위해서
애초에 집의 여부를 입력받을 때 방문할 수 없는 곳을 미리 방문처리해줬다.

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

int arr[30][30];
bool visited[30][30];
vector<int> result;
int cnt = 0;

void DFS(int x, int y)
{
	cnt++;
	visited[x][y] = true;
	if (visited[x + 1][y] && visited[x - 1][y] && visited[x][y - 1] && visited[x][y + 1]) {
		return;
	}

	if (!visited[x + 1][y]) DFS(x + 1, y);
	if (!visited[x - 1][y]) DFS(x - 1, y);
	if (!visited[x][y - 1]) DFS(x, y - 1);
	if (!visited[x][y + 1]) DFS(x, y + 1);
}

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

	int n;
	cin >> n;

	memset(visited, true, sizeof(visited));

	string input;
	for (int i = 1; i <= n; i++) {
		cin >> input;
		for (int j = 1; j <= input.size(); j++) {
			arr[i][j] = input[j-1] - '0';
			if (arr[i][j] == 1) 
				visited[i][j] = false;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!visited[i][j]) {
				cnt = 0;
				DFS(i, j);
				result.emplace_back(cnt);
			}
		}
	}

	sort(result.begin(), result.end());
	cout << result.size() << endl;
	for (int& r : result) cout << r << '\n';
}