bfs를 이용해 인접한 1끼리 묶어 사이즈 보기

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

int map[10][10];
bool visit[10][10];

int startx, starty;
int customernum = 0;

int sz = 0;
queue<pair<int, int>> q;

vector<int> bfs() {
    vector<int> ans;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 0 || visit[i][j] == 1) continue; //0이거나 방문시 패스
            visit[i][j] = 1;
            q.push(make_pair(i, j)); 
            sz++;
            while (!q.empty()) {
                pair<int, int> p = q.front();
                q.pop();
                int x = p.first;
                int y = p.second;
                
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                    if (map[nx][ny] == 0 || visit[nx][ny] == 1) { visit[nx][ny] = 1; continue; }
                    q.push(make_pair(nx, ny));
                    visit[nx][ny] = 1;
                    sz++;
                }
            }

            ans.push_back(sz);
            sz = 0;
        }
    }

    sort(ans.begin(), ans.end());
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }


    vector<int> v = bfs();
    for (auto a : v) {
        cout << a << " ";
    }
    return 0;
}

JAVA 버전

import java.util.Scanner;
import java.util.*;

class Pair {
	int x, y;
    Pair(int x, int y) {
    	this.x = x;
        this.y = y;
    }
}

class Main {
	static int[] dx= {0, 0, =1, 1};
    static int[] dy= {1, -1, 0, 0};
    static int num;
    static int[][] map = new int[10][10];
    static int[][] visit = new int[10][10];
    static int sz=0;
    static Queue<Pair> q = new LinkedList<>();
    static Vector<Integer> v = new Vector<Integer>();
    
    private Static Vector<Integer> dfs() {
    	for(int i=0; i<num; i++) {
        	for(int j=0; j<num; j++) {
            	if(map[i][j] == 0 || visit[i][j] == 1) continue;
                
                visit[i][j] = 1;
                q.add(new Pair(i, j));
                sz++;
                
                while(q.size() > 0) {
                	Pair pr = q.peek();
                    q.remove();
                    int x = pr.x;
                    int y = pr.y;
                    
                    for(int ii=0; ii<4; ii++) {
                    	int nx = x + dx[ii];
                        int ny = y + dy[ii];
                        if(nx<0 || ny<0 || nx>= num || ny>=num) continue;
                        if(map[nx][ny] == 0 || visit[nx][ny] == 1) {
                        	visit[nx][ny] = 1;
                            continue;
                        }
                        q.add(new Pair(nx,ny));
                        visit[nx][ny] = 1;
                        sz++;
                    }
                }
                v.add(sz);
                sz = 0;
            }
        }
                
        Collections.sort(v);
        return v;
    }
    
    privatd static void solution (int sizeOfMatrix, int[][] matrix) {
    	for(int i=0; i<sizeOfMatrix; i++) {
        	for(int j=0; j<sizeOfMatrix; j++) {
            	map[i][j] = matrix[i][j];
    		}
        }
        num = sizeOfMatrix;
        Vector<Integer> answer = dfs();
        
        System.out.println(answer.size());
        for(int i=0; i<answer.size(); i++) {
        	System.out.print(answer.get(i) + " ");
        }
    }
}