[BOJ] 2583. 영역 구하기

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

2583번: 영역 구하기

 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 

라고 나와있지만 정확한 좌표가 중요한 것은 아니라서 그냥 신경안쓰고 풀었다.

 

풀이

1. 사각형의 좌표를 입력받아서 사각형을 칠해준다.(1로 채운다)
2. 직사각형 내부를 제외한 나머지 부분을 구해야 하므로 값이 0인 곳에 대해서 DFS를 실행했다.
3. 연결요소를 구분하기 위해 연결된 부분들에 번호를 붙여준다.
4. 각 번호가 붙여진 곳들의 개수를 세서 cnt 배열에 넣어준후 출력.

 

 

import java.util.*;

public class Main {
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		int ans[][] = new int[n][m];
		int arr[][] = new int[n][m];
        
		for(int i=0; i<k; i++) {
			int lx = sc.nextInt();
			int ly = sc.nextInt();
			int rx = sc.nextInt();
			int ry = sc.nextInt();
			for(int j=lx; j<rx; j++) { //사각형 채우기
				for(int l=ly; l<ry; l++) {
					arr[l][j] = 1;
				}
			}
		}
        
		int count=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j] == 0 && ans[i][j] == 0){
					dfs(i,j,arr, ans, ++count, n, m); //dfs가 실행될때마다 count값 증가
				}
			}
		}	
		
		System.out.println(count);
		int cnt[] = new int[count];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(ans[i][j] != 0) {
					cnt[ans[i][j]-1] +=1;
				}
			}
		}
        
		Arrays.sort(cnt);
		for(int i=0; i<count; i++) {
			System.out.print(cnt[i]+" ");
		}
	}
    
	static void dfs(int i, int j, int[][] arr, int[][] ans, int count, int n, int m) {
		ans[i][j] = count; //번호 붙여준다
		for(int k=0; k<4; k++) {
			int x = i+dx[k];
			int y = j+dy[k];
			if(x >=0 && y>=0 && x < n && y < m) {
				if(arr[x][y] == 0 && ans[x][y] == 0) {
					dfs(x, y, arr, ans, count, n, m);
				}
			}
		}
	}
}