영역 구하기

일단 먼저 떠오른것은 Connected component && DFS && 좌표계 변환 정도가 떠올랐다.

예전에 win32API하면서 좌표계 변환하는거 많이 하다보니까 디버깅 잡으면서 변환하니까 이부분은 금방됨 (ChageMT 함수이다)

그리고 입력을 받을 때마다 1로 채워주고 거기에다가 DFS돌려주었다.

처음에는 row * col 전체 면적에다가 넓이를 뺄려고했는데 Connected Component각각의 넓이를 구해야해서 connected Component갯수를 인덱스로 하여 ret라는 배열에 sum을 넣어 주었다.

여기서 sum은 DFS함수가 호출 된 순서이다.

DFS가 호출 되었다는 것은 계속 파고 들어간다는 말이니까.

cpp 코드

#include <iostream>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 101

int row, col, cs, cnt = 0, sum = 0, ret[MAX];
int lby, lbx, rty, rtx;
int arr[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

void ChangeMT(int ly, int lx, int ry, int rx)
{
	lby = row - ly; lbx = lx;
	rty = row - ry; rtx = rx;
}

bool Cango(int y, int x)
{
	if (y >= row || y < 0 || x >= col || x < 0 || arr[y][x] == 1) return false;
	return true;
}

void DFS(int y, int x)
{
	visited[y][x] = 1;
	++sum;
	
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if (Cango(ny, nx) == false) continue;
		if (visited[ny][nx]) continue;
		DFS(ny, nx);
	}
}

void DFS_ALL()
{
	for (int y = 0; y < row; ++y)
	{
		for (int x = 0; x < col; ++x)
		{
			if (arr[y][x] == 1) continue;
			if (Cango(y, x) == false) continue;
			if (visited[y][x]) continue;
			DFS(y, x);
			ret[cnt++] = sum;
			sum = 0;
		}
	}
}

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

	cin >> row >> col >> cs;
	
	for (int i = 0; i < cs; ++i)
	{
		cin >> lbx >> lby >> rtx >> rty;
		ChangeMT(lby, lbx, rty, rtx);
		
		for (int y = 0; y < row; ++y)
		{
			for (int x = 0; x < col; ++x)
			{
				if (arr[y][x] == 1) continue;
				if ((y >= rty && y < lby) && (x >= lbx && x < rtx))
				{
					arr[y][x] = 1;
				}
			}
		}
	}

	DFS_ALL();
	cout << cnt << endl;
	sort(ret, ret + cnt);
	for (int i = 0; i < cnt; ++i) cout << ret[i] << " ";

	return 0;
}

수업 코드

내가짠 코드 가만히 생각해보니까 ChangeMT사용할 필요가 없었다.

그냥 입력받은 대로 다 채우고 DFS 돌리면 되는 거였음...

DFS의 반환형 ❗

지금은 ret를 반환을 하기 때문에 int형인데

이거 좀 중요한듯..

DFS의 재귀 호출이 다 끝나고 나면은 ret을 제일 마지막에 반환을 하게되니까 DFS의 반환형을 int로 걸어줌.

저기 ret += dfs(ny, nx);하는 부분이

지금 위의 그림을 예시로 이해를 하도록 하자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 101

int a[MAX][MAX], m, n, k, xx1, xx2, yy1, yy2, visited[MAX][MAX];
const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {-1, 0, 1, 0};
vector<int> ret;


bool Cango(int y, int x)
{
	if (y < 0 || y >= m || x < 0 || x >= n || visited[y][x] == 1) 
		return false;
	return true;
}
int DFS(int y, int x)
{
	visited[y][x] = 1;
	int ret = 1;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		if (a[ny][nx] == 1) continue;
		ret += DFS(ny, nx);
	}
	return ret;
}

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)
	{
		cin >> xx1 >> yy1 >> xx2 >> yy2;
		for (int x = xx1; x < xx2; ++x)
		{
			for (int y = yy1; y < yy2; ++y)
			{
				a[y][x] = 1;
			}
		}
	}
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (a[i][j] != 1 && visited[i][j] == 0) ret.push_back(DFS(i, j));
		}
	}

	sort(ret.begin(), ret.end());
	cout << ret.size() << endl;
	for (int a : ret) cout << a << " ";
	

	return 0;
}