백준 2583

백준 2583 : 영역 구하기

1. dfs의 진행 과정을 어느정도 파악하고 있어야 하는 문제였다.
2. dfs를 진행하며, 방문할때마다 영역의 넓이를 1씩 더하며 진행하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int m, n, k;
int board[101][101], visited[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int cnt;
vector<int> cntArr;


void fillBoard(int sx, int sy, int ex, int ey) {
	for(int i=sy; i<ey; i++) {
		for(int j=sx; j<ex; j++) {
			board[i][j]=1;
		}
	}	
}

void printBoard() {
	for(int i=m-1; i>=0; i--) {
		for(int j=0; j<n; j++) {
			cout<<board[i][j]<<' ';
		}
		cout<<'\n';
	}
}

void dfs(int y, int x) {
	visited[y][x]=1;
	
	for(int i=0; i<4; i++) {
		int ny = y+dy[i];
		int nx = x+dx[i];
		
		if(ny<0 || nx<0 || ny>=m || nx>=n || visited[ny][nx]) {
			continue;
		}
		
		if(board[ny][nx]==0) {
			cnt++;
			dfs(ny, nx);
		}
	}
	
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	

	cin>>m>>n>>k;
	for(int i=0; i<k; i++) {
		int sx, sy, ex, ey;
		cin>>sx>>sy>>ex>>ey;
		
		fillBoard(sx, sy, ex, ey);
	}
	
//	printBoard();

	int ans=0;

	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) {
			if(board[i][j]==0 && !visited[i][j]) {
				cnt=1;
				ans++;
				dfs(i, j);	
				cntArr.push_back(cnt);
			}
		}
	}
	
	sort(cntArr.begin(), cntArr.end());
	
	cout<<ans<<'\n';
	for(int i=0; i<cntArr.size(); i++) {
		cout<<cntArr[i]<<' ';
	}
	
	return 0;
}