문제링크

풀이

보통 문제들과 달리 M과 N이 반대로 주어진다는 점만 잘 고려하면 쉽게 풀 수 있는 문제이다. 주어지는 직사각형의 좌표에 따라 이차원 배열에 1로 표시해주고, 이중반복문을 통해 표시되지 않은 부분(0)에서는 BFS를 통해 영역의 넓이를 구하였다. bfs를 돌 때 방문하는 곳은 1로 표시를 함으로써 visited 배열을 따로 사용하지 않았다.

이런 문제를 행과 열을 잘 구분해야할 거 같다.
실제로 이게 헷갈려서 풀이하는데 너무 시간을 많이 써버리기도 했고..

코드

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

public class sol2583 {
    static int m, n, k;
    static int[][] map;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<Point> q;
    static int count = 0;
    static int[] size;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new int[m][n];
        size = new int[10001];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            fill(x1, y1, x2, y2);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0) {
                    size[count] = bfs(i, j);
                    count++;
                }
            }
        }
        Arrays.sort(size, 0, count);
        System.out.println(count);
        for (int i = 0; i < count; i++) {
            sb.append(size[i]).append(" ");
        }
        System.out.println(sb);
    }

    public static void fill(int x1, int y1, int x2, int y2) {
        for (int i = y1; i < y2; i++) {
            for (int j = x1; j < x2; j++) {
                map[i][j] = 1;
            }
        }
    }

    public static int bfs(int x, int y) {
        q = new LinkedList<>();
        int sum = 1;
        q.add(new Point(x, y));
        map[x][y] = 1;
        while (!q.isEmpty()) {
            Point curr = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    continue;
                }
                if (map[nx][ny] == 0) {
                    q.add(new Point(nx, ny));
                    map[nx][ny] = 1;
                    sum++;
                }
            }
        }
        return sum;
    }

    public static class Point {
        int x, y;

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

}