[BOJ] 2583. 영역 구하기

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int M,N,K;
	static int map[][];
	static boolean discovered[][];
	static int dx[]= {1,0,-1,0};
	static int dy[]= {0,1,0,-1};
	public static void main(String[] args) {
		M=sc.nextInt();
		N=sc.nextInt();
		K=sc.nextInt();
		map=new int[M][N];
		discovered=new boolean [M][N];
		Rectangle[]rec=new Rectangle[K];
		
		for (int i = 0; i < K; i++) {
			rec[i]=new Rectangle(sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt());
		}
		
		for (int i = 0; i < rec.length; i++) {
			for (int j = rec[i].h1; j < rec[i].h2; j++) {
				for (int k = rec[i].w1; k < rec[i].w2; k++) {
					map[j][k]=1; 
				}
			}
		}
		
		int cnt=0;
		List<Integer> list=new ArrayList<Integer>();
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if(map[i][j]==0 && !discovered[i][j]) {
					list.add(bfs(i,j,cnt));
					cnt++;
				}
			}
		}
		
		Collections.sort(list);
		
		System.out.println(cnt);
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i)+" ");
		}
	}
	
	public static int bfs(int x,int y,int cnt) {
		int count=0;
		Queue<Point> q=new LinkedList<>();
		q.add(new Point(x,y));
		discovered[x][y]=true;
		map[x][y]=2+cnt;
		while(!q.isEmpty()) {
			Point c=q.poll();
			count++;
			int nx;
			int ny;
			for (int i = 0; i < 4; i++) {
				nx=c.x+dx[i];
				ny=c.y+dy[i];
				if(nx<0 || ny<0 || nx>M-1 || ny>N-1) continue;
				for (int j = 0; j < discovered.length; j++) {
					if(map[nx][ny]==0 && !discovered[nx][ny]) {
						discovered[nx][ny]=true;
						map[nx][ny]=2+cnt;
						q.add(new Point(nx,ny));
					}
				}
			}
		}
		return count;
	}
	
	
	public static class Rectangle{
		int w1,h1,w2,h2;
		Rectangle(int w1,int h1,int w2,int h2){
			this.w1=w1;
			this.h1=h1;
			this.w2=w2;
			this.h2=h2;
		}
	}
	public static class Point{
		int x,y;
		Point(int x,int y){
			this.x=x;
			this.y=y;
		}
	}
}