[백준] 2667 - 단지 번호 붙이기

island의 DFS와 매우 유사하다. 다만 DFS안에서 value를 0으로 바꾸는 과정에서 바꾼 횟수를 세어 arraylist에 넣는게 추가되었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

    static int[][] arr;
    static int N;
    static ArrayList<Integer> arrayList = new ArrayList<>();
    static int temp = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = tmp.charAt(j) - '0';
            }
        }

        int danzi = 0;
        for(int i=0; i< N ; i++) {
            for(int j=0; j< N; j++) {
                if(arr[i][j] == 1) {
                    arr[i][j] = 0;
                    danzi++;
                    DFS(i, j);
                    arrayList.add(temp);
                    temp = 1;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(danzi).append("\n");
        Collections.sort(arrayList);

        for(var x : arrayList) {
            sb.append(x).append("\n");
        }
        System.out.println(sb.toString());

    }
    public static void DFS(int x, int y) {
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >=0 && nx < N && ny >= 0 && ny < N && arr[nx][ny] == 1) {
                temp++;
                arr[nx][ny] = 0;
                DFS(nx, ny);
            }
        }
    }

}