[ 백준 ] 2583번: 영역 구하기

•  문제

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

2583번: 영역 구하기

---

• 풀이법 ( 알고리즘 )

이차원 배열을 선언하고 입력받은 직사각형의 꼭짓점의 좌표들을 이용해 직사각형의 넓이만큼 이차원 배열에 저장해주었다. 이후 이차원 배열을 돌며 각 영역의 넓이를 구해 ans 배열에 넣어주었다.

---

•  풀이 - C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int m, n, k, cnt; // m * n 크기 모눈 종이 , k : 직사각형의 개수
int paper[101][101];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
bool visit[101][101];
vector <int> ans;

void dfs(int x, int y)
{
	if(paper[x][y] || visit[x][y]) return;

	visit[x][y] = true;
	cnt++;

	for (int i = 0; i < 4; i++)
	{
		int X = dx[i] + x;
		int Y = dy[i] + y;

		if (X < 0 || X >= m || Y < 0 || Y >= n || visit[X][Y] || paper[X][Y]) continue;
		dfs(X, Y);
	}

}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	//input
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++)
	{
		int leftBottomX, leftBottomY;
		int rightTopX, rightTopY;

		cin >> leftBottomX >> leftBottomY >> rightTopX >> rightTopY;

		for (int j = leftBottomY; j < rightTopY; j++)
		{
			for (int k = leftBottomX; k < rightTopX; k++)
				paper[j][k] = 1;
		}

	}

	/*for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
			cout << paper[i][j] << " ";
		cout << "\n";
	}*/

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!paper[i][j] && !visit[i][j])
			{
				dfs(i, j);
				ans.push_back(cnt);
				cnt = 0;
			}
		}
	}

	cout << ans.size() << "\n";
	sort(ans.begin(), ans.end());

	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";

}