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

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

문제 출처 : https://www.acmicpc.net/problem/2667

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Problem2667 {
    static int map[][];
    static int visited[][];
    static int dx[] = {0, 0, -1, 1}; //상하좌우
    static int dy[] = {-1, 1, 0, 0};
    static int n;
    
    public static void bfs() {
        Queue<Integer> qx = new LinkedList<Integer>();
        Queue<Integer> qy = new LinkedList<Integer>();
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        for (int i = 0; i < n; i++) {
            
            int x, y;
            int ax, ay;
            int count;
            
            for (int j = 0; j < n; j++) {
                count = 1;
                
                if(map[i][j] == 1) {
                    x = i;
                    y = j;
                    
                    qx.add(x);
                    qy.add(y);
                    
                    visited[x][y] = 1;
                    
                    while(!qx.isEmpty() && !qy.isEmpty()) {
                        x = qx.poll();
                        y = qy.poll();
                        
                        for (int z = 0; z <= 3; z++) { // 상하좌우
                            ax = x + dx[z];
                            ay = y + dy[z];
                            
                            if(ax >= 0 && ay >= 0 && ax < n && ay < n) {
                                if(map[ax][ay] == 1 && visited[ax][ay] == 0) {
                                    count++;
                                    map[ax][ay] = 0;
                                    qx.add(ax);
                                    qy.add(ay);
                                }
                                
                                visited[ax][ay] = 1;
                            }
                        }
                    }
                    arr.add(count);
                }
            }
        }
        
        Collections.sort(arr);
        System.out.println(arr.size());
        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        
        map = new int[n+1][n+1];
        visited = new int[n+1][n+1];
        
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            
            for (int j = 0; j < str.length(); j++) {
                map[i][j] = str.charAt(j) - 48;
            }
        }
        
        
        bfs();
    }
 
}