영역 구하기========

📍 문제 설명

 

 

💡 접근

영역에 맞게 직사각형을 그리고나서 분리된 영역의 갯수와 넓이를 구하면 되는 문제였다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k, answer, area;
    static int[][] board,dis,ch;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[] combi;
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        m = kb.nextInt();
        n = kb.nextInt();
        k = kb.nextInt();
        board = new int[m][n];
        //0,2 -> 2행 0열 4,0 -> 0행 4열
        for(int i = 0; i < k; i++) {
            int leftDownX = kb.nextInt(); //행
            int leftDownY = kb.nextInt(); //열
            int rightUpX = kb.nextInt(); //행
            int rightUpY = kb.nextInt(); //열
            for(int j = leftDownY; j < rightUpY; j++) {
                for(int k = leftDownX; k < rightUpX; k++) {
                    board[j][k] = 1;
                }
            }
        }

        //각 영역에 넓이 담기
        ArrayList<Integer> list = new ArrayList<>();

        //이제 0인 부분을 탐색하여 각 영역의 넓이를 탐색
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                area = 0;
                if(board[i][j] == 0) {
                    answer++;
                    area++;
                    board[i][j] = 1;
                    T.solution(i, j);
                    list.add(area);
                }
            }
        }
        Collections.sort(list);
        System.out.println(answer);
        for(int x : list) System.out.print(x + " ");
    }

    private void solution(int x, int y) {
        //상하좌우를 확인하여 빈 영역이면 answer 증가 및 눈금채우기
        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 && board[nx][ny] == 0) {
                area++;
                board[nx][ny] = 1;
                solution(nx, ny);
            }
        }
    }

}