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

문제

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

2583번: 영역 구하기

 

코드

BFS를 이용해서 풀면된다.

import java.util.*;
import java.io.*;

public class Main {
	static int m, n;
	static boolean check[][];
	static int dx [] = {1,0,-1,0};
	static int dy [] = {0,1,0,-1};
	static int area [];
	static int board[][];
	static int idx = 0;
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		 
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		board = new int [m][n];
		check = new boolean [m][n];
		area = new int[n*m];
		
		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 y = y1; y <y2; y++) {
				for(int x = x1; x < x2; x++) {
					board[y][x] = 1;
				}
			}
		}
			
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(board[i][j] == 0 && !check[i][j])
					bfs(j, i);
			}
			
		}
		
		Arrays.sort(area, 0, idx);
		System.out.println(idx);
		for(int i=0;i<idx;i++) {
			System.out.print(area[i] + " ");
		}
		
	}		
	
	static void bfs(int x, int y) {
		Queue<int []> que = new LinkedList<>();
		
		que.add(new int[] {x,y});
		check[y][x] = true;
		int count = 1;
		
		while(!que.isEmpty()) {
			int [] cur = que.poll();
			
			for(int i=0;i<4;i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				if(nx <0 || ny < 0 || ny >= m || nx >= n) continue;
				if(board[ny][nx] == 1 || check[ny][nx]) continue;
				
				que.add(new int [] {nx, ny});
				check[ny][nx] = true;
				count++;
			}
			
		}
		
		area[idx++] = count;
	}
	
}