[Softeer] 장애물 인식 프로그램 (lv.2)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409 

Softeer

2021

---

import java.util.*;
import java.io.*;
 
 
public class Main
{
   public static int N;
    public static int[][] arr;
    public static boolean[][] vtd;
    public static ArrayList<Integer> list;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
 
    public static void solve(int pp, int qq) {
        Queue<int[]> q = new LinkedList<>();
        vtd[pp][qq] = true;
        q.add(new int[]{pp, qq});
 
        int size = 1;
        while(!q.isEmpty()) {
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
 
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if(nx < 0 || ny < 0 || nx >= N || ny >= N || arr[nx][ny] == 0 || vtd[nx][ny]) continue;
                else {
                    vtd[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                    size++;
                }
            }
        }
        list.add(size);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
 
        N = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        vtd = new boolean[N][N];
        list = new ArrayList<>();
 
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            String str = st.nextToken();
            for(int j = 0; j < N; j++) {
                arr[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }
 
        int count = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++){
                if(!vtd[i][j] && arr[i][j] == 1) {
                    count++;
                    solve(i, j);
                }
            }
        }
        System.out.println(count);
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for (Integer integer : list) sb.append(integer).append("\n");
        System.out.println(sb.toString());
    }
}