백준 2583 영역 구하기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

주어진 직사각형 부분을 제외한 영역의 개수와 그영역들의 넓이를 구하는 문제입니다.

 

저는 이문제를 dfs를 통해서 해결 하였고 문제가 좌표가 수학에서의 평면좌표 형식으로 주어져서 배열에서는 돌려서(?) 생각을 하시면 될거 같습니다.

 

나머지는 크게 어려운 부분이 없습니다. main함수에서 dfs가 호출된 횟수가 영역의 개수이고 dfs안에서 마지막 지점에 도착할때까지 진행된 횟수가 그영역의 넓이입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[101][101];
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
vector<int> v;
int M,N,K;


int dfs(int a, int b, int num) {
	
	arr[a][b] = 1;

	for(int i = 0; i < 4; i++) {
		int x = a + nextx[i];
		int y = b + nexty[i];
		
		if(x < 0 || x >= N || y < 0 || y >= M)
			continue;
		
		if(!arr[x][y])
			num = dfs(x, y, num+1);
	}
	return num;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> M >> N >> K;
	int lx,ly;
	int rx,ry;
	int areanum = 0;
	
	for(int i = 0; i < K; i++) {
		cin >> lx >> ly >> rx >> ry;
		for(int j = 0; j < ry - ly; j++) 
			for(int k = 0; k < rx - lx; k++)
				arr[lx+k][ly+j] = 1;
	}
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			if(!arr[i][j]) {
				v.push_back(dfs(i, j, 1));
				areanum++;
			}
	
	sort(v.begin(), v.end());
	cout<<areanum<<'\n';
	for(auto n: v)
		cout<<n<<' ';
	return 0;
}