백준 - 2667번

 

풀이

 

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

 

public class Main {

 

      static int[][] arr;

      static boolean[][] check;

      static int num = 0;

      static int[] changeX = {1, -1, 0, 0};

      static int[] changeY = {0, 0, 1, -1};

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

 

            BufferedReader br = new BufferedReader ( new InputStreamReader (System.in));

 

            num = Integer.parseInt(br.readLine());

            int countNum = 0;

            arr = new int[num][num]; // 입력받는 집 여부 배열 초기화

            int answer[] = new int[num*num];

            check = new boolean[num][num]; // 방문 배열 초기화

            // 입력받기

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

                  String str = br.readLine();

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

                        arr[i][j] = Integer.parseInt(Character.toString(str.charAt(j)));

                  }

            }

            // 세대 카운트

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

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

                        if((arr[i][j] == 1) && (check[i][j] != true)) {

                              int total = Count(i, j);

                              answer[countNum] = total;

                              countNum++;

                        }

                  }

            }

            Arrays.sort(answer);

            System.out.println(countNum);

            for(int i=answer.length-countNum; i<answer.length; i++) {

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

            }

      }

 

      private static int Count(int a, int b) { // a : x좌표, b : y좌표

            int count = 1;

            check[a][b] = true; // 방문 확인

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

                  int chX = a + changeX[i];

                  int chY = b + changeY[i];

 

                  if(chX < num && chY < num && chX >= 0 && chY >= 0) {

                        if(check[chX][chY] != true && arr[chX][chY] == 1) {

                              count += Count(chX, chY);

                        }

                  }

            }

            return count;

      }

}