[C/C++] 코드업(codeup) 4572번 영역 구하기

▽문제 바로가기

https://codeup.kr/problem.php?id=4572

영역 구하기

---

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100이하의 자연수이다.

둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y 좌표값과 오른쪽 위 꼭짓점의 x, y 좌표값이 빈칸을 사이에 두고 차례로 주어진다.

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

입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 

 

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다.

둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

문제 풀이

 

색칠을 해야 해서 까다로워 보였으나 사실 그렇지 않습니다.

입력을 보면 "직사각형의 왼쪽 아래 꼭짓점의 x, y 좌표값과 오른쪽 위 꼭짓점의 x, y 좌표값이 빈칸을 사이에 두고 차례로 주어진다."라고 되어있습니다. 차례로 주어지니 뒤에 입력되는 값이 앞에 입력되는 값보다 큰 값입니다.

 

또한, 이 문제가 쉬운 이유는 문제의 <그림>을 참고하면 사분면의 그림으로 배열의 형태와 다르지면 배열처럼 풀더라도 그림이 반대로 뒤집어질 뿐 결과는 똑같기 때문입니다.

 

위점을 참고하면 색칠만 해주면 똑같은 탐색문제!

 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int m, n, k;
int arr[101][101] = {0,};
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0}; 

int dfs(int row, int col){
	//범위 밖이면 리턴
	if(row==-1||col==-1||row==m||col==n) return 0;
	
	//색칠되어있다면 리턴
	if(arr[row][col]==1) return 0;
	
	//색칠안되어있다면 탐색
	arr[row][col] = 1;	//중복 탐색 방지
	return 1 + dfs(row+dy[0], col+dx[0]) + dfs(row+dy[1], col+dx[1]) + dfs(row+dy[2], col+dx[2]) + dfs(row+dy[3], col+dx[3]);
}

int main(){
	
	scanf("%d%d%d", &m, &n, &k);
	
	int a, b, c, d;
	for(int i=0;i<k;i++){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		//색칠
		for(int row=b;row<d;row++){
			for(int col=a;col<c;col++){
				arr[row][col] = 1; 
			}
		}
	}
	
	int cnt = 0;
	vector <int> v;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			//색칠안되어있다면 탐색
			if(arr[i][j]==0){
				v.push_back(dfs(i, j));
				cnt++;
			}
		}
	}
	
	sort(v.begin(), v.end());
	printf("%d\n", cnt);
	for(int i=0;i<v.size();i++) printf("%d ", v[i]);
	
	return 0;
}