[알고리즘] 영역 구하기

구현 방식

• 방문하지 않았고, 직사각형 내부가 아닌 부분을 탐색해서 BFS를 진행한다. –> BFS 를 한번 진행할 때마다 넓이를 계산할 수있는 영역 개수가 추가되는 것임
• BFS를 진행하면서 탐색 가능한(방문하지 않았고, canGo 가 가능한) 노드를 발견하면 넓이 area를 1 증가시킨다.

struct Pos
{
	Pos()
	{
	}
	Pos(int y, int x)
	{
		this->y = y;
		this->x = x;
	}
	int y;
	int x;
};

void solution(int N, int M);
int bfs(int N, int M, Pos& currPos);
bool canGo(Pos& nextPos, int N, int M);

int graph[101][101] = {};
bool visited[101][101] = {};
Pos surround[4] = { {-1, 0},{1, 0},
					{0,-1},{0,1}};


int main()
{
	int N, M, K;

	cin >> M >> N >> K;

	for (int i = 0; i < K; ++i)
	{
		Pos leftBehindPos , rightUpPos;
		cin >> leftBehindPos.x >> leftBehindPos.y;
		cin >> rightUpPos.x >> rightUpPos.y;
		for (int y = leftBehindPos.y; y < rightUpPos.y; y++)
			for (int x = leftBehindPos.x; x < rightUpPos.x; x++)
				graph[y][x] = 1;
	}

	solution(M, N);

}


void solution(int M, int N )
{
	vector<int> result;
	for (int y = 0; y < M; y++)
		for (int x = 0; x < N; x++)
		{
			Pos nextPos = { y, x };
			if (canGo(nextPos, M, N) && !visited[nextPos.y][nextPos.x])
			{
				result.push_back(bfs(M, N, nextPos));
			}

		}

	sort(result.begin(), result.end());
	cout << result.size() << "\n";
	for_each(result.begin(), result.end(), [](int x) {cout << x << " "; });
}

int bfs(int N, int M, Pos& currPos)
{
	int area = 0;
	queue<Pos> q;
	q.push(currPos);
	visited[currPos.y][currPos.x] = true;
	area++;

	while (!q.empty())
	{
		Pos currPos = q.front();
		q.pop();
		
		for (Pos& surr : surround)
		{
			Pos nextPos = { currPos.y + surr.y , currPos.x + surr.x };
			if (canGo(nextPos, N, M) && !visited[nextPos.y][nextPos.x])
			{
				q.push(nextPos);
				visited[nextPos.y][nextPos.x] = true;
				area++;
			}
		}

	}

	return area;

}


bool canGo(Pos& nextPos,int N, int M)
{
	if (nextPos.y < 0 || N <= nextPos.y)
		return false;
	if (nextPos.x < 0 || M <= nextPos.x)
		return false;
	// 1 이면 도형으로 칠해진 경우
	if (graph[nextPos.y][nextPos.x] == 1)
		return false;
	if (graph[nextPos.y][nextPos.x] == 0)
		return true;
	return false;
}