[JAVA] 백준 2583- 영역 구하기

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

2583번: 영역 구하기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int n, m, size;
    static int[][] arr;

    public static void dfs(int x, int y) {

        arr[x][y] = 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) continue;

            if (arr[nx][ny] == 0) {
                size++;
                dfs(nx, ny);
            }

        }
    }

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

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

        arr = new int[m][n];

        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());

            for (int j = y1; j < y2; j++) {
                for (int l = x1; l < x2; l++) {
                    arr[j][l] = 1;
                }
            }
        }

        ArrayList<Integer> list = new ArrayList<>();

        int cnt = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 0) {
                    size = 1;
                    cnt++;
                    dfs(i, j);
                    list.add(size);
                }
            }
        }
        Collections.sort(list);

        System.out.println(cnt);
        for (int x : list) {
            System.out.print(x + " ");
        }

    }
}

 

 

입력받은 좌표에 따라 좌표 범위 내에 있는 칸들을 1로 채운다.

이 때 상하가 뒤집혀서 채워지지만 어차피 구하고자 하는건 0 부분의 넓이이므로 굳이 그림처럼 맞추진 않았다.

모든칸을 탐색할 때 size를 1로 초기화 해놓고 dfs를 돌면서 0인 부분을 만날 때마다 넓이를 증가시킨다.