백준 2583 영역구하기

백준 2583 영역구하기

구현 전 생각

n과 M이 100미만의 크기로 주어져서 완전 탐색을 이용하고 그중에 DFS를 이용해서 현재 점에서 사방탐색으로 이동 할 수 있는 점을 탐색하고 탐색 할때마다 그 배열안에 cnt 값을 넣고 더 이상 이동 할 수 없는 경우 cnt++하여서 마킹을 하고 나누어진 공간의 갯수를 출력하고 cnt만큼의 배열을 만들어서 배열안에 각각의 cnt값에 해당하는 넓이만큼을 찾은 뒤 정렬하여 출력해볼것이다.

아쉬운점

1. N,M이 조금 다르게 나와 있어서 입력을 받는데 애를 먹었다.

2. DFS 탐색을 하러 가기 전에 그 해당 값을 미리 변경 해주어야 한다는 점을 놓쳐서 조금 오래 걸렸던 문제!!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{
	static int M,N,K,cnt;
	static int map[][];
	static boolean isSelected[][];
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void DFS(int x, int y) {
		
		for (int i = 0; i < 4; i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(nx<0||ny<0||nx>=N||ny>=M) continue;
			if(map[nx][ny]==-1) continue;
			if(isSelected[nx][ny]) continue;
			isSelected[nx][ny] = true;
			map[nx][ny]=cnt;
			DFS(nx,ny);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N =Integer.parseInt(st.nextToken());
		M =Integer.parseInt(st.nextToken());
		K =Integer.parseInt(st.nextToken());
		isSelected= new boolean [N][M];
		map= new int[N][M];
		cnt = 0;
		for (int i = 0; i <K; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int sx =Integer.parseInt(st.nextToken());
			int sy =Integer.parseInt(st.nextToken());
			int ex =Integer.parseInt(st.nextToken());
			int ey =Integer.parseInt(st.nextToken());
			
			for (int j = sy; j <ey; j++) {
				for (int j2 = sx; j2 <ex; j2++) {
					
					map[j][j2]=-1;
					isSelected[j][j2]=true;
					
				}
			}
		}
		for (int j = 0; j < N; j++) {
			for (int j2 = 0; j2 < M; j2++) {
				if(!isSelected[j][j2]) {
				isSelected[j][j2]=true;
				map[j][j2]=cnt;
				DFS(j,j2);
				cnt++;
			}
		 }
		}
		//System.out.println(Arrays.deepToString(map));
		int[] numbers = new int[cnt+1];
		for (int i = 0; i <=cnt; i++) {
			int Lcnt=0;
			for (int j = 0; j < N; j++) {
				for (int j2 = 0; j2 < M; j2++) {
					if(map[j][j2]==i)
					{
						Lcnt++;
					}
				}
			}
			
		numbers[i]=Lcnt;
		}
		Arrays.sort(numbers);
		System.out.println(cnt);
		for(int z:numbers) {
			if(z!=0)
			System.out.print(z+" ");
		}
	}
	
}