📙 [Algo] 24.01.02 알고리즘

2583번: 영역 구하기

문제 요약
M*N 크기의 모눈종이
모눈종이 위에 k개의 직사각형을 그림
그려진 직사각형을 기준으로 분리된 영역 각각의 넓이를 구하는 프로그램 작성


시간 제한 
1초

입력
M N K

- 모두 100 이하의 자연수

K의 줄에 직사각형 왼쪽 아래 꼭짓점의 x,y 좌표와 오른쪽 위 꼭짓점의 x,y 좌표가 주어짐

직사각형이 모눈정이 전체를 채우는 경우는 없음

출력
첫 번째 줄 : 분리된 영역의 개수 출력
두 번째 줄 : 각 영역의 넓이 오름차순 정렬

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int M, N, K;
    static int[][] arr;
    static boolean[][] visited;
    static int[] deltaX = {-1, 1, 0, 0};
    static int[] deltaY = {0, 0, -1, 1};
    static int s;

    static void dfs(int row, int col){
        visited[row][col] = true;
        s++;

        for(int dir=0; dir<4; dir++){
            int mrow = row + deltaX[dir];
            int mcol = col + deltaY[dir];

            if(mrow<0 || mcol<0 || M<=mrow || N<=mcol) continue;

            if(!visited[mrow][mcol]){
                if(arr[mrow][mcol] == 0){
                    dfs(mrow, mcol);
                }
            }
        }

    }

    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());
        K = Integer.parseInt(st.nextToken());
        arr = new int[M][N];

        while(K-->0){
            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 y=y1; y<y2; y++){
                for(int x=x1; x<x2; x++){
                    arr[y][x] = 1;
                }
            }

        }


        visited = new boolean[M][N];

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

        System.out.println(cnt);
        Collections.sort(sList);
        for(int i=0; i<sList.size(); i++){
            System.out.print(sList.get(i) + " ");
        }

    }
}