백준 2583번 영역 구하기 [ Java ]

2583번: 영역 구하기

BFS를 이용하여 풀었습니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dx = new int[]{1, 0, -1, 0};
        int[] dy = new int[]{0, 1, 0, -1};
        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();
        String[] in = br.readLine().split(" ");
        int M = Integer.parseInt(in[0]);
        int N = Integer.parseInt(in[1]);
        int K = Integer.parseInt(in[2]);
        int[][] field = new int[M][N];
        boolean[][] visited = new boolean[M][N];
        while(K-- >0){
            int[] rect = Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .toArray();
            for (int i=rect[1]; i<rect[3]; i++)
                for (int j=rect[0]; j<rect[2]; j++)
                    field[i][j] = 1;
        }

        for (int i=0; i<M; i++){
            for (int j=0; j<N; j++){
                if (visited[i][j] || field[i][j]==1) continue;
                count++;
                Queue<int[]> Q = new LinkedList<>();
                visited[i][j] = true;
                Q.offer(new int[]{i, j});
                int max = 0;
                while (!Q.isEmpty()){
                    max++;
                    int[] cur = Q.poll();
                    for (int dir=0; dir<4; dir++){
                        int nx = cur[1] + dx[dir];
                        int ny = cur[0] + dy[dir];
                        if (nx<0 || nx>=N || ny<0 || ny>=M) continue;
                        if (visited[ny][nx] || field[ny][nx]==1) continue;
                        visited[ny][nx] = true;
                        Q.offer(new int[]{ny, nx});
                    }
                }
                result.add(max);
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(count+"\n");
        result.stream().sorted().forEach(i->sb.append(i+" "));
        System.out.print(sb);
    }
}