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

https://www.acmicpc.net/problem/2583

시나리오

• 사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표를 입력받아 grid의 가로 시작 좌표, 세로 시작좌표를 구하고 가로 길이와 세로 길이를 구한다.
• 그 다음 구한 정보를 토대로 각 사각형을 grid에 그린다. fillRect()
• 사각형을 모두 그린 다음에는 grid를 완전탐색하며 bfs를 통해 빈 영역을 조사한다. 이 때 queue에 들어가는 모든 좌표는 곧 빈 영역의 개수가 되므로,
• while문 반복횟수만큼 카운트하면 그것이 빈 영역의 넓이가 된다.
  위 과정을 통해 분리된 영역의 개수와 각 영역의 넓이를 구할 수 있다.

핵심 아이디어

• 사각형 그리기: 입력으로 주어진 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점을 grid좌표로 매핑하고 가로, 세로 길이를 구해 그만큼 반복문을 돌며 grid를 채운다.
• 빈 영역 넓이 구하기: 빈 영역을 찾을 때마다 그 영역은 더 이상 접근하지 못하기 때문에 while문의 반복횟수는 곧 빈 영역의 넓이와도 같다. 즉, 큐에 들어가는 요소의 개수는 하나의 빈 영역의 넓이인 것이다.

코드

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

class Main {
    private static final List<Integer> areas = new ArrayList<>();
    private static final int[] dy = {-1, 0, 1, 0};
    private static final int[] dx = {0, 1, 0, -1};

    private static boolean[][] grid;
    private static int cnt;
    private static int M;
    private static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        int K = Integer.parseInt(input[2]);

        grid = new boolean[M][N];

        for (int i = 0; i < K; i++) {
            String[] coord = br.readLine().split(" ");
            //입력의 좌표는 x,y꼴 ==col,row
            int[] leftDown = {Integer.parseInt(coord[0]), Integer.parseInt(coord[1])};
            int[] rightUp = {Integer.parseInt(coord[2]), Integer.parseInt(coord[3])};
            //아래 좌표는 y,x꼴 == row,col
            int[] widthStart = {M - leftDown[1] - 1, leftDown[0]};
            int[] heightStart = {M - rightUp[1], rightUp[0] - 1};
            int width = Math.abs(leftDown[0] - rightUp[0]);
            int height = Math.abs(leftDown[1] - rightUp[1]);

            fillRect(widthStart, width, heightStart, height);
        }
        search();

        System.out.println(cnt);
        areas.stream().sorted().forEach(e -> System.out.printf("%d ", e));
    }

    private static void search() {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!grid[i][j]) {
                    grid[i][j] = true;
                    cnt++;
                    areas.add(bfs(i, j));
                }
            }
        }
    }

    private static void fillRect(int[] widthStart, int width, int[] heightStart, int height) {
        //사각형 가로 채우기
        for (int w = widthStart[1]; w < widthStart[1] + width; w++) {
            grid[widthStart[0]][w] = true;
        }
        //사각형 세로 채우기
        for (int h = heightStart[0]; h < heightStart[0] + height; h++) {
            for (int w = widthStart[1]; w < widthStart[1] + width; w++) {
                grid[h][w] = true;
            }
        }
    }

    private static int bfs(int startY, int startX) {
        int area = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startY, startX});

        while (!q.isEmpty()) {
            int[] e = q.poll();
            int y = e[0];
            int x = e[1];
            area++;

            for (int k = 0; k < 4; k++) {
                int _y = y + dy[k];
                int _x = x + dx[k];

                if (isValidCoord(_y, _x) && !grid[_y][_x]) {
                    q.offer(new int[]{_y, _x});
                    grid[_y][_x] = true;
                }
            }
        }
        return area;
    }

    private static boolean isValidCoord(int y, int x) {
        return 0 <= y && y < M && 0 <= x && x < N;
    }

}