Baekjoon2583-영역구하기

백준 사이트 2583 - 영역구하기 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

쉽게 접할 수 있는 BFS문제입니다. 백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

1. 분리된 사각형을 세야한다. 또한 각 사각형의 넓이를 저장할 변수가 필요. -> vector, 동적할당
2. map을 그려야하는 input의 최대값이 100이므로 배열은 전역변수로 처리가 가능하다.
3. 문제에서는 맵이 왼쪽 아래에서 시작하지만, 일반적인 2차원 배열은 왼쪽 위부터 시작한다.

해결법은 간단하다 위아래를 뒤집는다 생각하고 문제를 풀어나가면 된다.

---

5. code 및 설명

#include<iostream>// 입출력을 위한
#include<vector>// vector에 사각형 넓이를 저장하기 위해
#include<queue>// bfs를 위한 queue
#include<algorithm>// 정렬함수를 쓰기 위해
using namespace std;

const int MAX = 100; //최대치는 100

bool arr[MAX][MAX] = { false };// map
bool v[MAX][MAX] = { false }; // visit
int N, M, K; 
int Rcount = 0;// 사각형 갯수
vector<int> area; // 사각형 넓이 저장 변수
int dx[4] = { -1,0,1,0 }; //맵을 이동하기 위한 좌표값
int dy[4] = { 0,1,0,-1 }; //맵을 이동하기 위한 좌표값

//사각형을 그림
void makeRectangle(int x1, int y1, int x2, int y2)
{
	for (int i = x1; i < x2; ++i)
	{
		for (int j = y1; j < y2; ++j)
			arr[j][i] = true;
	}
}

void bfs(int i, int j)
{
	if (arr[i][j] == true)//사각형 범위일경우
		return;
	else if (v[i][j] == true)//이미 들린 경우
		return;
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));
	v[i][j] = true;
	//다 걸렀으면 빈 사각형이므로 갯수를 더해줌.
	++Rcount;
	//0부터가 아닌 1인 이유는 해당 사각형도 세줘야하기 때문이다.
	int areanum = 1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < N && 0 <= newY && newY < M && arr[newX][newY] == false && v[newX][newY] == false)
			{
				q.push(make_pair(newX, newY));
				v[newX][newY] = true;
				//사각형을 넓이를 세줌
				++areanum;
			}
		}

	}
	area.push_back(areanum);
	

}

void Solve()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			bfs(i, j);
		}
	}
	cout << Rcount<<'\n';
	//문제에서 요청한 정렬
	sort(area.begin(), area.end());
	vector<int>::iterator it;

	for (it = area.begin(); it != area.end(); ++it)
	{
		cout << *it << " ";
	}
}
void Input()
{
	cin >> N >> M >> K;
	for (int i = 0; i < K; ++i)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		makeRectangle(x1, y1, x2, y2);
	}
	
}

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

	Input();
	Solve();

	return 0;
}

---