[알고리즘 문제 풀이] 백준 2667 단지번호붙이기 (BFS/DFS)

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

import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;

public class Main{

    static int N;
    static int[][]arr;
    static boolean[][] visited;

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

    static int count;
    static int dangi;

    static ArrayList<Integer> ans;

    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];
        visited=new boolean[N][N];
        ans =new ArrayList<>();

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            String k = st.nextToken();
            for(int j=0;j<N;j++){
                arr[i][j]=Integer.parseInt(k.substring(j,j+1));
            }
        }
        dangi = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(arr[i][j]==0) continue;
                else if (arr[i][j]==1 && !visited[i][j]){
                    count=1;
                    dangi++;
                    dfs(i,j);
                    ans.add(count);

                }
            }
        }
        Collections.sort(ans);
        System.out.println(dangi);
        for(int i=0;i<ans.size();i++){
            System.out.println(ans.get(i));
        }

    }

    static void dfs(int x,int y){

        visited[x][y]=true;
        arr[x][y]=dangi;
        for(int i=0;i<4;i++){
            int movedX = dx[i]+x;
            int movedY = dy[i]+y;

            /*if(movedX>= 0 && movedY>=0 && movedX <N && movedY<N && !visited[movedX][movedY] && arr[movedX][movedY]==1){
                count++;
                dfs(movedX,movedY);
            }*/
            if(movedX<0 || movedX >=N || movedY<0 ||movedY>=N) continue;

            if(visited[movedX][movedY]) continue;

            if(arr[movedX][movedY]==0) continue;

            count++;
            dfs(movedX,movedY);

        }


    }
}