[BOJ] 2583 - 영역 구하기 (Java)

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

1. 문제

• MxN 크기의 이차원 평면에 몇 개의 직사각형이 그려져 있을 때, 직사각형으로 나누어지지 않은 영역의 크기를 구하는 문제
  

2. Idea

• 주어진 MxN 평면에서 직사각형으로 나누어지지 않은 영역들을 DFS를 사용하여 탐색하고, 각 영역의 크기를 계산하여 출력
• 이를 위해 직사각형을 표시하는 map 배열과 방문 여부를 체크하는 visited 배열을 사용하며, DFS를 통해 연결된 영역을 탐색

3. 풀이

3.1. 변수 선언

static int n; // 행의 개수
static int m; // 열의 개수
static boolean[][] map; // 직사각형의 위치를 표시하는 지도
static boolean[][] visited; // 방문 여부를 체크하는 배열
static int dx[] = {-1, 1, 0, 0}; // 상하좌우 이동을 위한 x좌표 변화량
static int dy[] = {0, 0, -1, 1}; // 상하좌우 이동을 위한 y좌표 변화량
static List<Integer> nums; // 각 영역의 크기를 저장하는 리스트
static int count; // 현재 영역의 크기를 저장하는 변수

3.2. 직사각형 그리기

• 입력으로 주어진 직사각형의 좌표를 읽어서 map 배열에 직사각형이 그려진 부분을 true로 표시
• 직사각형의 좌표는 (a1, b1)에서 (a2, b2)까지입니다. 여기서 (a2, b2)는 포함되지 않기 때문에 -1로 처리

for (int i = 0; i < k; i++) {
    st = new StringTokenizer(br.readLine());
    int a1 = Integer.parseInt(st.nextToken());
    int b1 = Integer.parseInt(st.nextToken());
    int a2 = Integer.parseInt(st.nextToken()) - 1;
    int b2 = Integer.parseInt(st.nextToken()) - 1;

    for (int j = a1; j <= a2; j++) {
        for (int l = b1; l <= b2; l++) {
            map[l][j] = true;
        }
    }
}

3.3. 영역 탐색 및 크기 계산

• 모든 좌표를 순회하면서, 방문하지 않았고 직사각형이 아닌 부분에서 DFS를 시작
• DFS를 통해 연결된 모든 영역을 탐색하며 count 증가
• 탐색이 끝나면 nums 리스트에 count를 추가하고, count를 초기화

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (!visited[i][j] && !map[i][j]) {
            dfs(i, j);
            nums.add(count);
            count = 0;
        }
    }
}

3.4. DFS 함수

• 현재 좌표를 방문 처리하고 count를 증가
• 상하좌우로 이동하며, 범위를 벗어나지 않고, 방문하지 않았으며, 직사각형이 아닌 부분에 대해 재귀적으로 DFS를 수행

private static void dfs(int x, int y) {
    visited[x][y] = true;
    count++;

    for (int i = 0; i < 4; i++) {
        int nowX = x + dx[i];
        int nowY = y + dy[i];

        if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
            if (!visited[nowX][nowY] && !map[nowX][nowY]) {
                dfs(nowX, nowY);
            }
        }
    }
}

3.5. 결과 출력

• nums 리스트를 오름차순으로 정렬
• 영역의 개수를 출력
• 각 영역의 크기를 출력

Collections.sort(nums);
System.out.println(nums.size());
for (Integer num : nums) {
    System.out.print(num + " ");
}

4. 전체코드

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

public class Main {
    static int n;
    static int m;
    static boolean[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static List<Integer> nums;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        map = new boolean[n][m];
        visited = new boolean[n][m];
        nums = new ArrayList<>();
        count = 0;

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken()) - 1;
            int b2 = Integer.parseInt(st.nextToken()) - 1;


            for (int j = a1; j <= a2; j++) {
                for (int l = b1; l <= b2; l++) {
                    map[l][j] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && !map[i][j]) {
                    dfs(i, j);
                    nums.add(count);
                    count = 0;
                }
            }
        }

        Collections.sort(nums);
        System.out.println(nums.size());
        for (Integer num : nums) {
            System.out.print(num + " ");
        }
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;
        count++;

        for (int i = 0; i < 4; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                if (!visited[nowX][nowY] && !map[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}