백준 2667번 C++

#include <iostream>

#include <string>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

const int MAX = 26;

int n;

string arr[MAX];

vector<int> answer;

typedef struct {

int a, b;

}Move;

Move mv[4] = { {1,0},{-1,0},{0,1},{0,-1} };

bool checkfinish() {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (arr[i][j] == '1')

return false;

}

}

return true;

}

int bfs(int a,int b) {

int answer = 1;

queue<pair<int, int>> q;

q.push(make_pair(a, b));

arr[a][b] = '0';

while (!q.empty()) {

int x = q.front().first;

int y = q.front().second;

q.pop();

for (int k = 0; k < 4; k++) {

int mx = x + mv[k].a;

int my = y + mv[k].b;

if (mx >= 0 && mx < n && my >= 0 && my < n) {

if (arr[mx][my] == '1') {

arr[mx][my] = '0';

answer++;

q.push(make_pair(mx, my));

}

}

}

}

return answer;

}

int main(void) {

cin >> n;

for (int i = 0; i < n; i++)

cin >> arr[i];

int counts = 0;

if (!checkfinish()) {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (arr[i][j] == '1') {

answer.push_back(bfs(i, j));

counts++;

}

}

}

}

cout << counts << endl;

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

for (int i = 0; i < answer.size(); i++) {

cout << answer[i] << endl;

}

}