문제

이해

MxN 크기의 모눈종이에 입력받은 사각형을 색칠한다.

색칠된 사각형으로 분리된 각 영역의 개수와 크기를 출력한다.

접근

좌표상의 특정 영역 넓이를 구하는 방법으로는 BFS가 있다.

우선, 입력받은 사각형을 평면상에 색칠해야 한다.

평면은 boolean 2차원 배열을 이용해서 색칠된 공간은 true로 표기한다.

모든 사각형을 색칠하면 (0, 0) ~ (M, N) 까지 색칠되지 않은 영역을 확인한다.

배열 순회 중에 색칠되지 않은 영역을 만나면 그 좌표를 기준으로 BFS를 수행한다.

탐색 조건으로는 색칠된 공간은 탐색하지 않도록 한다.

탐색한 공간은 다음 순회시에 탐색할 필요가 없기 때문에 true로 표기하고 BFS가 끝나면 과정에서 측정한 넓이를 ArrayList에 삽입한다.

(M, N)까지 순회가 끝나면 ArrayList에 저장된 넓이 정보와 영역 개수를 출력하면 된다.

코드

package java_baekjoon;

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

public class prob2583 {
    static int M;
    static int N;
    static int K;
    static int[] d_row = { 0, -1, 0, 1 };
    static int[] d_col = { -1, 0, 1, 0 };
    static boolean[][] square;
    static ArrayList<Integer> area_arr = new ArrayList<>();

    static class xy {
        int x;
        int y;

        public xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        square = new boolean[M][N];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int y1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            for (int j = x1; j < x2; j++) {
                for (int k = y1; k < y2; k++) {
                    square[j][k] = true;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (square[i][j]) {
                    continue;
                }
                int area = 0;
                Queue<xy> q = new LinkedList<>();
                q.add(new xy(i, j));
                area++;
                square[i][j] = true;

                while (!q.isEmpty()) {
                    xy now = q.poll();

                    for (int k = 0; k < 4; k++) {
                        int new_x = now.x + d_row[k];
                        int new_y = now.y + d_col[k];

                        if (new_x >= 0 && new_x < M && new_y >= 0 && new_y < N && !square[new_x][new_y]) {
                            area++;
                            q.add(new xy(new_x, new_y));
                            square[new_x][new_y] = true;
                        }
                    }
                }
                area_arr.add(area);
            }
        }

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

과정이 좀 많아서 코드가 길어졌지만 그다지 어려운 문제는 아니다.

BFS를 이용한 넓이 측정의 기초적인 문제이다.

결과