2667 단지번호붙이기

단순 무식한 방법이 먹힌듯 하다.

map을 초기화 할 때 1이 입력되는 좌표들은 모두 Q에 push !

큐를 팝하면서 연결되어있는 부분들을 탐색 !

그 과정에서 집의 수를 세어준다 !

코드:

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

int N;

int D[26][26];

int visited[26][26];

int px[4] = { 1, 0, -1, 0 }; // down right up left

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

struct pos{

int x;

int y;

};

int cnt;

int total;

queue<pos> Q;

char tmp[26];

void dfs(int x, int y){

if (visited[x][y] == 1) return;

else visited[x][y] = 1;

cnt++;

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

int x_ = x + px[i];

int y_ = y + py[i];

if (x_ < 0 || x_ >= N || y_ < 0 || y_ >= N) continue;

if (D[x_][y_] == 0) continue;

if (D[x_][y_] == 1 && visited[x_][y_] == 0){

dfs(x_, y_);

}

}

}

int main(){

cin >> N;

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

cin >> tmp;

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

D[i][j] = tmp[j] - '0';

if (D[i][j] == 1) Q.push({ i, j });

}

}

vector<int> V;

while (!Q.empty()){

int nx = Q.front().x;

int ny = Q.front().y;

Q.pop();

if (visited[nx][ny] != 1){

dfs(nx, ny);

V.push_back(cnt);

cnt = 0; total++;

}

}

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

cout << total << endl;

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

cout << V[i] << endl;

}

system("pause");

return 0;

}