단지 번호붙이기

[입력]

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000


[출력]

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

3

7

8

9





public class Main_단지번호붙이기 {

static int N;

static final int[] dr = new int[]{1,-1,0,0};

static final int[] dc = new int[]{0,0,-1,1};

public static void main(String[] args) throws Exception{

Scanner sc = new Scanner(System.in);

N = sc.nextInt();

sc.nextLine();

int[][] pan = new int[N+1][N+1];

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

char[] tmp = sc.nextLine().toCharArray();

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

pan[i][j] = (tmp[j-1] == '0'? 0:1);

}

}

int[] dangiCntArr = new int[N*N];

int[][] visit = new int[N+1][N+1];

int danginum = 1;

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

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

if(pan[i][j] == 1 && visit[i][j] == 0){

dangiCntArr[danginum-1] = bfs(pan, visit, new PairD(i, j, 0), danginum);

danginum = danginum +1;

}

}

}

System.out.println(danginum-1);

Arrays.sort(dangiCntArr);

for(int i=0; i<dangiCntArr.length; i++){

if(dangiCntArr[i] == 0) continue;

System.out.println(dangiCntArr[i]);

}

}

public static int bfs(int[][] pan, int[][] visit, PairD startPos, int danginum){

Queue<PairD> q = new LinkedList<PairD>();

q.add(startPos);

visit[startPos.r][startPos.c] = danginum;

int grp = 1;

while(!q.isEmpty()){

PairD p = q.remove();

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

int pr = p.r + dr[i];

int pc = p.c + dc[i];

if(pr < 1 || pc < 1 || pr > N || pc > N){

continue;

}

if(pan[pr][pc] == 1 && visit[pr][pc] == 0){

q.add(new PairD(pr, pc, p.step+1));

visit[pr][pc] = danginum;

grp++;

}

}

}

return grp;

}

}


class PairD{

int r;

int c;

int step;

public PairD(int r, int c, int step){

this.r = r;

this.c = c;

this.step = step;

}

}




public class Main {


static int N;

static char[][] a;

static int[][] visit;

static int sol;

static int[] cnt;


static class st {

int i, j;


st(int a, int b) {

i = a;

j = b;

}

}


static st[] Queue;

static int Wp, Rp;


static void In_Queue(int i, int j) {

Queue[Wp++] = new st(i, j);

}


static st Out_Queue() {

return Queue[Rp++];

}


static int FF(int si, int sj) {

int house = 0;

int[] di = { -1, 1, 0, 0 };

int[] dj = { 0, 0, -1, 1 };


Wp = 0;

Rp = 0;


// 시작점을 큐에 넣기

In_Queue(si, sj);

visit[si][sj] = 1;

house++;


while (Wp > Rp) {

st out = Out_Queue();

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

int ni = out.i + di[k];

int nj = out.j + dj[k];

// 범위 초과이면 continue

if (ni < 1 || ni > N || nj < 1 || nj > N)

continue;

// 집이 아니면 continue

if (a[ni][nj] != '1')

continue;

// 방문했으면 continue

if (visit[ni][nj] == 1)

continue;

// 방문

In_Queue(ni, nj);

visit[ni][nj] = 1;

house++;

}

}


return house;

}


public static void main(String[] args) {

Scanner sc = new Scanner(System.in);


// 입력

N = sc.nextInt();

a = new char[N + 10][N + 10];

visit = new int[N + 10][N + 10];

cnt = new int[N * N + 10];

Queue = new st[N * N + 10];

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

a[i] = ("\0" + sc.next()).toCharArray();

}


// Flood Fill

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

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

if (a[i][j] != '1')

continue;

if (visit[i][j] == 1)

continue;

cnt[sol++] = FF(i, j);

}

}


// 오름차순 정렬

for (int i = 0; i < sol - 1; i++) {

for (int j = i + 1; j < sol; j++) {

if (cnt[i] > cnt[j]) {

int temp = cnt[i];

cnt[i] = cnt[j];

cnt[j] = temp;

}

}

}


// 출력

System.out.println(sol);

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

System.out.println(cnt[i]);

}


sc.close();

}