영역 구하기

---

문제풀이

1. 나눠진 영역의 어느 한점 부터 인접한 점으로 탐색을 이어나간다.
2. 탐색이 끝나면 영역갯수를 1개 늘리고, 탐색한 넓이를 기억해둔다.

코드풀이

1. 백준의 예시그림에서는 (0, 0) 왼쪽 아래에 위치해 있지만, 우리가 디버깅을 하면서
   보는 배열은 왼쪽 위가 (0,0)이다. 차후에 디버깅을 위해서 여기서는 (0, 0)을 왼쪽 위로 두고 풀었다.
2. m를 y축, n을 x축으로 잡았다.
3. 두 점사이를 칠하려면, x1<=x<=x2, y1<=y<=y2를 잡고 칠하게되면 더 큰 사각형을 칠하게된다. 따라서 x1<=x<x2, y1<=y<y2 처럼 뒷부분 하나를 빼줘야 한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"

#define MAX 100+1
int m, n, k;
bool map[MAX][MAX];
bool visited[MAX][MAX];
int cnt;
int ans;
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
vector<int> area;

void dfs(int y, int x) {
	visited[y][x] = true;
	cnt++;

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

		if (nx<0 || nx>=n || ny<0 || ny>=m)
		{
			continue;
		}

		if (!map[ny][nx] && !visited[ny][nx])
		{
			dfs(ny, nx);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> m >> n >> k;
	while (k--)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = y1; i <= y2-1; i++)
		{
			for (int j = x1; j <= x2-1; j++)
			{
				map[i][j] = true;
			}
		}
	}

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

	cout << ans << endl;

	sort(area.begin(), area.end());
	for (int i = 0; i < area.size(); i++)
	{
		cout << area[i] << ' ';
	}
}

참고

https://coding-factory.tistory.com/595 벡터 정렬 방법, sort함수