[Java] 백준 2538 : 영역 구하기

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

2583번: 영역 구하기

---

주어진 배열을 왼쪽 위 상단이 0,0이 되도록 바꾸어 주었다. 

안 바꿔주고 그냥 계산해서 해도 정답은 나오지만 그냥 내가 문제를 파악하기 편하도록 바꿨다. 

static void fillArr(int sx,int sy,int ex,int ey) {
		//좌표변환 (sx,sy,ex,ey)-> (M-sy,sx,M-ey,ex)
		int startY=sx;
		int startX=M-sy;
		int endY=ex;
		int endX=M-ey;
			
		for(int i=endX;i<startX;i++) {
			for(int j=startY;j<endY;j++) {
				arr[i][j]=1;
			}
		}
	}//fillArr()

 

바꾸어 준다음에 배열을 이동하면서 비어있는 영역을 파악하기만 하면 된다. 

---

import java.util.*;

public class Main {

	static int N,M,K,cnt,val;
	static int[][] arr;
	static int[] dx= {0,0,-1,1};
	static int[] dy= {-1,1,0,0};
	 private static List<Integer> areas = new ArrayList<>();
	
	public static void main(String[] args){
	
		Scanner sc= new Scanner(System.in);
		M =sc.nextInt();
		N =sc.nextInt();
		K =sc.nextInt();
		arr= new int[M][N];
		
		for(int i=0;i<K;i++) {
			int sx=sc.nextInt();
			int sy=sc.nextInt();
			int ex=sc.nextInt();
			int ey=sc.nextInt();
			fillArr(sx,sy,ex,ey);		
		}

		for(int i=0;i<M;i++) {
			for(int j=0;j<N;j++) {
				if(arr[i][j]==0) {
					cnt ++;
					val=0;
					dfs(i,j);
					areas.add(val);
				}
			}
		}
		Collections.sort(areas);
		System.out.println(cnt);
		for(int a :areas)
			System.out.print(a+" ");
	
	}// main()
	
	static void fillArr(int sx,int sy,int ex,int ey) {
		//좌표변환 (sx,sy,ex,ey)-> (M-sy,sx,M-ey,ex)
		int startY=sx;
		int startX=M-sy;
		int endY=ex;
		int endX=M-ey;
			
		for(int i=endX;i<startX;i++) {
			for(int j=startY;j<endY;j++) {
				arr[i][j]=1;
			}
		}
	}//fillArr()
	
	static void dfs(int x, int y) {
		
		arr[x][y]=1;
		val++;
		
		for(int i=0;i<4;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0&&ny>=0&&nx<M&&ny<N) {
				if(arr[nx][ny]==0) {
					dfs(nx,ny);	
				}
			}
			
		}
				
	}//dfs()
	
}// class Main