[백준/C++] 2667번 : 단지번호붙이기

문제

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, cnt1, cnt2; //cnt1 = 단지 수, cnt2 = 단지 내 집의 수
string area[25];
vector<int> v;
bool isVisited[25][25];

int dirX[] = { 0, 1, 0, -1 };
int dirY[] = { 1, 0, -1, 0 };

void dfs(int y, int x) {
	isVisited[y][x] = true;
	cnt2++;

	for (int i = 0; i < 4; i++) {
		int curY = y + dirY[i];
		int curX = x + dirX[i];

		if (curX < 0 || curY >= n || curY <0 || curY >= n) continue;
		if (isVisited[curY][curX] == false && area[curY][curX] == '1')
			dfs(curY, curX);
	}
}

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

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (isVisited[i][j] == false && area[i][j] == '1') {
				cnt2 = 0;
				dfs(i, j);
				v.push_back(cnt2);
				cnt1++;
			}
		}
	}

	cout << cnt1 << '\n';

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << '\n';
	}

	return 0;
}