작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class area_check_2583 {
    static int[][] arr;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int m, n;
    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());
        int rectangleCount = Integer.parseInt(st.nextToken());

        arr = new int[m][n];
        for (int[] row : arr) {
            Arrays.fill(row, 0);
        }

        for (int i = 0; i < rectangleCount; i++) {
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());
            drawRectangle(sx, sy, ex, ey);
        }

        List<Integer> areas = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 0) {
                    areas.add(dfs(j, i));
                }
            }
        }

        Collections.sort(areas);
        System.out.println(areas.size());
        for (int area : areas) {
            System.out.print(area + " ");
        }
    }
    public static void drawRectangle(int sx, int sy, int ex, int ey) {
        for (int i = sy; i < ey; i++) {
            for (int j = sx; j < ex; j++) {
                arr[i][j] = 1;
            }
        }
    }
    public static int dfs(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || arr[y][x] != 0) {
            return 0;
        }

        arr[y][x] = 1;
        int count = 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            count += dfs(nx, ny);
        }

        return count;
    }
}

설명

자료구조

• 2차원 배열(arr): 입력받은 m × n 크기의 배열로, 각 요소는 해당 위치의 영역을 나타냅니다. 0은 미방문 영역, 1은 방문한 영역을 의미합니다.

• List<Integer> areas: 영역의 크기를 저장하기 위한 리스트입니다. DFS를 통해 계산된 각 영역의 크기가 리스트에 추가됩니다.

• dfs는 깊이 우선 탐색(Depth-First Search) 알고리즘을 구현한 메서드입니다. 이 알고리즘은 그래프나 트리 등의 자료구조에서 한 노드에서 출발하여 연결된 모든 노드를 재귀적으로 탐색하는 방법입니다.

dfs 메서드는 다음과 같이 작동합니다:

• 현재 위치의 좌표 (x, y)가 주어집니다.
• 기저 조건을 확인합니다. 만약 현재 위치가 배열의 범위를 벗어나거나 이미 방문한 영역인 경우, 탐색을 종료하고 0을 반환합니다.
• 현재 위치를 방문한 영역으로 표시합니다. (arr[y][x] = 1)
• 현재 영역의 크기를 1로 초기화합니다.
• 상하좌우 네 방향에 대해 재귀적으로 dfs를 호출하고 반환된 값을 현재 영역의 크기에 더합니다.
• 최종적으로 계산된 영역의 크기를 반환합니다.
• dfs 메서드는 drawRectangle 메서드에서 직사각형 영역을 표시한 배열 arr을 기반으로 실행되며, 방문하지 않은 영역(값이 0인 요소)을 탐색하여 해당 영역의 크기를 계산합니다. 이렇게 계산된 영역의 크기는 areas 리스트에 추가되어 나중에 정렬 및 출력됩니다.

따라서 dfs는 재귀적인 탐색을 통해 영역의 크기를 계산하는데 사용되는 자료구조로 볼 수 있습니다.

로직

• 입력값 받기:

  • 첫 번째 줄에서 m과 n 값을 입력받습니다. m은 배열의 행(row) 개수를 나타내고, n은 배열의 열(column) 개수를 나타냅니다.
  • 두 번째 줄에서는 직사각형의 개수를 나타내는 rectangleCount 값을 입력받습니다.
  • 그 이후에는 직사각형들의 좌표값을 입력받습니다.

• 배열 초기화:

  • m × n 크기의 배열(arr)을 생성하고, 모든 요소를 0으로 초기화합니다.

• 직사각형 영역 표시:

  • 입력받은 직사각형들의 좌표값을 기반으로 배열(arr)에서 해당 영역을 1로 표시합니다.
  • drawRectangle() 메서드에서 시작점과 끝점을 받아 직사각형의 영역을 1로 채우는 작업을 수행합니다.

• 영역의 개수와 크기 계산:

  • 배열(arr)을 탐색하면서 0인 요소를 발견하면, 해당 영역에 대해서 DFS(Depth-First Search)를 수행하여 영역의 크기를 계산합니다.
  • dfs() 메서드에서는 재귀적으로 상하좌우 인접한 요소들을 탐색하면서 영역의 크기(count)를 증가시킵니다.

• 영역의 크기 정렬 및 출력:

  • 계산된 영역의 크기들을 오름차순으로 정렬한 후, 영역의 개수와 정렬된 영역의 크기들을 출력합니다.

다른 언어로

자바스크립트

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let arr;
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let m, n;

function main() {
  rl.question('', (input) => {
    const [mm, nn, rectangleCount] = input.split(' ').map(Number);
    m = mm;
    n = nn;

    arr = new Array(m);
    for (let i = 0; i < m; i++) {
      arr[i] = new Array(n).fill(0);
    }

    for (let i = 0; i < rectangleCount; i++) {
      rl.question('', (rectangleInput) => {
        const [sx, sy, ex, ey] = rectangleInput.split(' ').map(Number);
        drawRectangle(sx, sy, ex, ey);
      });
    }

    const areas = [];
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (arr[i][j] === 0) {
          areas.push(dfs(j, i));
        }
      }
    }

    areas.sort((a, b) => a - b);
    console.log(areas.length);
    console.log(areas.join(' '));

    rl.close();
  });
}

function drawRectangle(sx, sy, ex, ey) {
  for (let i = sy; i < ey; i++) {
    for (let j = sx; j < ex; j++) {
      arr[i][j] = 1;
    }
  }
}

function dfs(x, y) {
  if (x < 0 || x >= n || y < 0 || y >= m || arr[y][x] !== 0) {
    return 0;
  }

  arr[y][x] = 1;
  let count = 1;

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    count += dfs(nx, ny);
  }

  return count;
}

main();

파이썬

def draw_rectangle(sx, sy, ex, ey):
    for i in range(sy, ey):
        for j in range(sx, ex):
            arr[i][j] = 1

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m or arr[y][x] != 0:
        return 0

    arr[y][x] = 1
    count = 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        count += dfs(nx, ny)

    return count

m, n, rectangle_count = map(int, input().split())
arr = [[0] * n for _ in range(m)]

for _ in range(rectangle_count):
    sx, sy, ex, ey = map(int, input().split())
    draw_rectangle(sx, sy, ex, ey)

areas = []
for i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            areas.append(dfs(j, i))

areas.sort()
print(len(areas))
print(*areas)