백준 2667 - 단지번호붙이기


Tags : DFS


문제

백준 2667 - 단지번호붙이기

image


풀이

image

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

int N;
int complex;
vector<int> ans;
int counting;
vector<string> apt;
bool chk[26][26];

int dX[4] ={-1, 1, 0, 0};
int dY[4] ={0, 0, -1, 1};

void DFS(int x, int y)
{
	chk[x][y] = true;
	++counting;

	for (int i = 0; i < 4; ++i)
	{
		int newX = x + dX[i];
		int newY = y + dY[i];

		if (newX < 0 || newX >= N
			|| newY < 0 || newY >= N)
			continue;

		if (apt.at(newX).at(newY) == '1' && !chk[newX][newY])
			DFS(newX, newY);
	}
}

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

	cin >> N;

	string input;

	for (int i = 0; i < N; ++i)
	{
		cin >> input;
		apt.push_back(input);
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (apt.at(i).at(j) == '1' && !chk[i][j])
			{
				DFS(i, j);
				ans.push_back(counting);
				counting = 0;
				++complex;
			}
		}
	}

	cout << complex << '\n';
	sort(ans.begin(), ans.end());
	for (int i = 0; i < (int)ans.size(); ++i)
	{
		cout << ans.at(i) << '\n';
	}
}