[JAVA]백준_2583_영역구하기

문제링크

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

2583번: 영역 구하기

 

 

 

package BOJ;

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_2583 {
    static int N,M,K;
    static int map[][];
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static int size;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken()); //세로
        N = Integer.parseInt(st.nextToken()); //가로
        K = Integer.parseInt(st.nextToken());

        map = new int[M][N];

        for(int k=0;k<K;k++){
            st = new StringTokenizer(br.readLine());
            //왼쪽아래 꼭짓점 x,y 오른쪽 위 꼭짓점 x,y
            int leftX = Integer.parseInt(st.nextToken());
            int leftY = Integer.parseInt(st.nextToken());
            int rightX = Integer.parseInt(st.nextToken());
            int rightY = Integer.parseInt(st.nextToken());

            //사각형 칠하기
            for(int i=leftY;i<rightY;i++){
                for(int j=leftX;j<rightX;j++){
                    map[i][j] =1;
                }
            }
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                //현재가 빈공간 && 방문하지 않았으면
                if(map[i][j] == 0){
                    size = 0;
                    dfs(i,j);
                    list.add(size);
                }
            }
        }

        Collections.sort(list);

        System.out.println(list.size());
        for(Integer size : list) System.out.print(size+" ");
    }

    static void dfs(int i,int j){
        map[i][j] = 1;
        size++;

        for(int d=0;d<4;d++){
            int nx = i + dx[d];
            int ny = j + dy[d];

            if(nx<0 || ny<0 || nx>=M || ny>=N|| map[nx][ny]>0) continue;

            if(map[nx][ny] == 0){
                 dfs(nx,ny);
            }
        }
    }
}