백준 2583 영역 구하기 C++

백준 2583 영역 구하기.

백준 2583번 "영역 구하기" 문제의 자세한 내용은 글 하단의 문제 링크를 참고하세요.

2583번 문제에 주어지는 입력 및 예시

입력: 

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

출력:

3
1 7 13

코드

백준 2583번 "영역 구하기" 문제의 코드입니다.

//2583
#include <bits/stdc++.h>
using namespace std;
vector<int> cnt;
int DirectionY[4] = {-1, 0, 1, 0};  // 위 오 아 왼
int DirectionX[4] = {0, 1, 0, -1};
int a[101][101];
bool visited[101][101];
int n,m;
int dfs(int y,int x){
	int t=1;
	visited[y][x]=1;
	for(int i=0;i<4;i++){
    	int _dx=x+DirectionX[i];
    	int _dy=y+DirectionY[i];
    	if(_dx<0||_dy<0||_dy>=n||_dx>=m||visited[_dy][_dx]) continue;
    	if(!a[_dy][_dx]) t+=dfs(_dy,_dx); 
	}
	return t;
}
int main() {
	int k,x1,y1,x2,y2;
	cin>>n>>m>>k; //x>>y>>k
	memset(visited,0,sizeof(visited));
	for(int t=0;t<k;t++){
    	cin>>x1>>y1>>x2>>y2;
    	for(int i=y1;i<y2;i++)
			for(int j=x1;j<x2;j++)
				a[i][j]=1;    
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(!a[i][j]&& !visited[i][j])
				cnt.push_back(dfs(i,j) ); //y,x   
	cout<<cnt.size()<<"\n";
	sort(cnt.begin(),cnt.end());
	for(auto v: cnt)
		cout<<v<<" ";
	return 0;
}

실행

위의 코드를 예제의 입력을 넣어 실행했을 때의 결과입니다.

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

2583번: 영역 구하기