[백준] 2667번 : 단지번호붙이기 (실버I)

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

2667번: 단지번호붙이기

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int N;
int map[25][25];
queue<int> q;

//arr은 단지내 아파트 개수 (인접한 1의 개수)를 저장할 배열
int arr[313];

//배열의 사이즈를 별도로 관리
int arrSize = 0;

int dr[4] = {1,-1,0,0}; 
int dc[4] = {0,0,1,-1};

// 좌표 r,c 가 N*N 정사각형 내에 있는지 확인해주는 함수
bool isInRange(int r, int c)
{
	if(r>=0 && r < N && c>=0 && c < N)
		return true;
	else
		return false;
}

// BFS 방식을 통하여,  map[r][c]와 연결되어있는 1들을 0으로 만든후 그 개수를 반환함
// 0으로 만들어 주는 방식을 통하여 별도의 저장공간을 사용하지 않았음 ex) visited[25][25]
int getSizeOfArea(int r, int c)
{
	int count = 1;
	int tr,tc;
	
	q.push(r);
	q.push(c);
	map[r][c] = 0;
	
	while(!q.empty())
	{
		tr = q.front(); q.pop();
		tc = q.front(); q.pop();
	
		for(int i= 0; i<4; i++)
		{
			if(isInRange(tr+dr[i],tc+dc[i]) && map[tr+dr[i]][tc+dc[i]] == 1)
			{
				q.push(tr+dr[i]);
				q.push(tc+dc[i]);
				// 0으로 만들어주는 코드의 위치를 유의하여 작성해야함. q에서 빼는 동시에 
				// 0으로 만들면 런타임 에러 발생
				map[tr+dr[i]][tc+dc[i]] = 0;
				count++;
			}
		}
	}
	
	return count;
}

void init()
{
	cin >> N;
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			scanf("%1d",&map[i][j]);
		}
	}
}


int main() {
	init();
	
	
	//모든 정사각형 내의 좌표들을 순환하며 진행
	//한번 카운팅된 좌표는 0으로 바뀌기 때문에 중복 발생 x
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(map[i][j] == 1)
			{
				arr[arrSize++] = getSizeOfArea(i,j);
			}
		}
	}
	
	//오름차순 정렬
	sort(arr,arr+arrSize);
	
	//배열의 사이즈 = 단지의 개수
	cout << arrSize << endl;
	
	
	//단지내 아파트 개수 출력
	for(int i=0; i<arrSize; i++)
	{
		cout << arr[i] << endl;
	}
	return 0;
}