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

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

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

vector<int>map[100];
vector<int>result;

int cnt = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int n;

struct Location {
	int x;
	int y;

	Location(int _x, int _y)
	{
		x = _x;
		y = _y;
	}
};

int main()
{
	cin >> n;
	string num;
	for (int i = 0; i < n; i++) 
	{
		cin >> num;
		for (int j= 0; j < n; j++)
		{
			int a = num[j]-'0';
			map[i].push_back(a);
		}
	}

	queue<Location> Q;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cnt = 0;
			if (map[i][j] == 1) //집인곳 
			{
				map[i][j] = 0;
				Q.push(Location(i, j)); ///큐에 넣고
				cnt++;
				while (!Q.empty())  //아파트인곳 근처 단지 형성되는 곳 찾기
				{
					Location tmp = Q.front();
					Q.pop();
					for (int k = 0; k < 4; k++) //4방향
					{
						int xx = tmp.x+dx[k];
						int yy = tmp.y+dy[k];

						if (xx < 0 || n <= xx || yy < 0 || n <= yy) //배열 범위 체크
							continue;
 						if (map[xx][yy] == 1) //아파트 추가 
						{ 
							map[xx][yy] = 0;
							cnt++;
							Q.push(Location(xx,yy));
						}
					}
				}
				result.push_back(cnt);//근처 다 찾으면 찾은 아파트 수 저장				
			}
		}
	}

	cout << result.size() << endl; //단지 수 출력

	sort(result.begin(), result.end()); //수 정렬

	for (auto a : result) { //출력
		cout << a << endl;
	}
	return 0;
}