[BOJ 2667번] 단지번호붙이기(C++)

테크케찰 2020. 9. 18. 20:48

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. �

www.acmicpc.net

#include <stdio.h>
#include<algorithm>
int arr[27][27] = { 0 };
int arr2[100] = { 0 };
int  n = 0;

void dfs(int x, int y)
{
	arr[y][x] = 0;
	if (arr[y][x+1] == 1)
		dfs(x + 1, y);
	if (arr[y][x - 1] == 1)
		dfs(x - 1, y);
	if (arr[y+1][x] == 1)
		dfs(x, y + 1);
	if (arr[y-1][x] == 1)
		dfs(x, y - 1);
	arr2[n]++;
}

int main(void)
{
	int size, cnt=0;
	scanf("%d", &size);
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			scanf("%1d", &arr[j][i]);
		}
	}
	for (int k = 0; k < size; k++)
	{
		for (int l = 0; l < size; l++)
		{
			if (arr[k][l] == 1)
			{
				dfs(l, k);
				cnt++;
				n++;
			}
		}
	}
	printf("%d\n", cnt);
	std::sort(arr2, arr2 + cnt);
	for (int m = 0; m < cnt; m++)
	{
		printf("%d\n", arr2[m]);
	}
}