⭐ 문제

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

🧐 시도

import java.util.*;

public class Main {
static int M, N, K;
static int[][] grid;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    M = sc.nextInt();
    N = sc.nextInt();
    K = sc.nextInt();

    grid = new int[M][N];
    visited = new boolean[M][N];

    for (int i = 0; i < K; i++) {
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        for (int x = x1; x < x2; x++) {
            for (int y = y1; y < y2; y++) {
                grid[y][x] = 1;
            }
        }
    }

    List<Integer> areas = new ArrayList<>();
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0 && !visited[i][j]) {
                areas.add(dfs(i, j));
            }
        }
    }

    Collections.sort(areas);
    System.out.println(areas.size());
    for (int area : areas) {
        System.out.print(area + " ");
    }
}

static int dfs(int x, int y) {
    visited[x][y] = true;
    int area = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < M && ny < N && grid[nx][ny] == 0 && !visited[nx][ny]) {
            area += dfs(nx, ny);
        }
    }

    return area;
}

}

📝 풀이

클래스 및 변수 선언:

javaCopypublic class RegionDivision {
static int M, N, K;
static int[][] grid;
static boolean[][] visited;
static List areas = new ArrayList<>();

M, N: 모눈종이의 크기
K: 직사각형의 개수
grid: 모눈종이를 표현하는 2차원 배열
visited: DFS 탐색 시 방문 여부를 체크하는 배열
areas: 각 분리된 영역의 넓이를 저장하는 리스트

메인 메소드:

javaCopypublic static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();

grid = new int[M][N];
visited = new boolean[M][N];

입력을 받아 변수들을 초기화합니다.

직사각형 영역 입력 및 채우기:

javaCopyfor (int i = 0; i < K; i++) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
fillRectangle(x1, y1, x2, y2);
}

각 직사각형의 좌표를 입력받아 fillRectangle 메소드로 grid에 표시합니다.

분리된 영역 찾기:

javaCopyfor (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 0 && !visited[i][j]) {
areas.add(dfs(i, j));
}
}
}

전체 grid를 순회하며 아직 방문하지 않은 빈 영역(0)에서 DFS를 시작합니다.

결과 출력:

javaCopyCollections.sort(areas);
System.out.println(areas.size());
for (int area : areas) {
System.out.print(area + " ");
}

찾은 영역들의 넓이를 정렬하고 출력합니다.

fillRectangle 메소드:

javaCopystatic void fillRectangle(int x1, int y1, int x2, int y2) {
for (int i = y1; i < y2; i++) {
for (int j = x1; j < x2; j++) {
grid[i][j] = 1;
}
}
}

입력받은 직사각형 영역을 grid에 1로 채웁니다.

dfs 메소드:

javaCopystatic int dfs(int x, int y) {
if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] == 1 || visited[x][y]) {
return 0;
}

visited[x][y] = true;
int area = 1;

area += dfs(x-1, y);
area += dfs(x+1, y);
area += dfs(x, y-1);
area += dfs(x, y+1);

return area;

}

재귀적으로 상하좌우를 탐색하며 연결된 빈 영역의 넓이를 계산합니다.
경계를 벗어나거나, 이미 채워진 영역(1)이거나, 이미 방문한 곳이면 0을 반환합니다.

이 코드는 분할 정복 방식으로 문제를 해결합니다. 직사각형으로 채워지지 않은 영역을 DFS로 탐색하여 각 분리된 영역의 넓이를 계산하고, 이를 정렬하여 출력합니다.