[C/C++ 백준 2583번] 영역 구하기 (Silver 1)

www.acmicpc.net/problem/2583

2583번: 영역 구하기

영역을 세는 문제에서, 영역의 넓이도 구하는 문제가 추가되었다. 그냥 각 함수에서 넓이에 관한 변수를 만들어 준뒤, vector에 넣어주었다가 나중에 한번에 정렬해주고 출력하자.

 

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int M, N, K, graph[100][100], ans=0;
int xmove[4]={-1,0,1,0};
int ymove[4]={0,1,0,-1};
vector <int> A;
void Search(int x, int y){
	if(graph[x][y]==1)
		return ;
	else{
		int F = 0;
		ans++;
		graph[x][y]=1;
		queue <pair<int, int>> q;
		q.push({x, y});
		while(!q.empty()){
			int tmpx = q.front().first;
			int tmpy = q.front().second;
			q.pop();
			F++;
			for(int i=0; i<4; i++){
				if((xmove[i]+tmpx >=0 && xmove[i]+tmpx<M) &&
				(ymove[i]+tmpy >=0 &&ymove[i]+tmpy<N)){
					if(graph[xmove[i]+tmpx][ymove[i]+tmpy]==0){
						q.push({xmove[i]+tmpx, ymove[i]+tmpy});
						graph[xmove[i]+tmpx][ymove[i]+tmpy] = 1;
					}
				}
			}
		}
		A.push_back(F);
	}	
}
int main(void){
	scanf("%d %d %d",&M ,&N, &K);
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			graph[i][j]=0;
		}
	}
	int x1, y1, x2, y2;
	for(int i=0; i<K; i++){
		scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
		for(int k=x1; k<x2; k++){
			for(int w=y1; w<y2; w++){
				graph[k][w] = 1;
			}
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			Search(i, j);
		}
	}
	printf("%d\n", ans);
	sort(A.begin(), A.end());
	for(int i=0; i<A.size(); i++)
		printf("%d ", A[i]);
}