백준 / 바킹독님의 문제집 / 영역 구하기(2583)

문제 설명

 

 

문제 해결

 

통상적으로 우리가 배열을 사용할 때, 아래쪽로 y값이 증가하고, 오른쪽으로 x값이 증가한다.

하지만 문제에서 사용하는 좌표계는 인간에게 맞춰져 있다.

일단 입력은 그대로 받고, 연산할 때 인간 기준으로 맞춰서 BFS를 실행하면 문제를 해결할 수 있다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <tuple>
#include <string>
#include <vector>
#include <algorithm>

// 문제에서 사용하는 좌표 시스템이 기존에 사용하던 방식이랑 다르다. 
// 기존은 아래, 오른쪽으로 숫자가 커졌다면 지금은 위, 오른쪽으로 숫자가 커지는 형태
// 입력은 기존에 사용하던 방식을 그대로 쓰고, BFS 탐색할 때는 좌표를 뒤집어 사용하면 된다.

#define x first
#define y second

using namespace std;

int M, N, K;
int map[100][100] {0};
int visit[100][100] {0};

queue<pair<int, int>> q;
pair<int, int> direction[4] = { make_pair(1,0), make_pair(0,1),make_pair(-1,0),make_pair(0,-1) };
vector<int> answer;

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	cin >> M >> N >> K;

	while (K--) // 모눈종이 색칠
	{
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		for (int i = y1; i < y2; i++)
		{
			for (int j = x1; j < x2; j++)
			{
				map[i][j] = -1;
			}
		}
	}

	for (int i = M - 1; i >= 0; i--) // BFS
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == 0 && map[i][j] != -1)
			{
				visit[i][j] = 1;
				q.push(make_pair(i, j));

				int count = 1;

				while (!q.empty())
				{
					auto current = q.front();
					q.pop();

					for (int i = 0; i < 4; i++)
					{
						int nx = current.x + direction[i].x;
						int ny = current.y + direction[i].y;

						if (nx < 0 || nx >= M || ny < 0 || ny >= N)
							continue;

						if (visit[nx][ny] != 0 || map[nx][ny] == -1)
							continue;

						visit[nx][ny] = 1;
						q.push(make_pair(nx, ny));
						count++;
					}
				}
				answer.push_back(count);
			}
		}
	}

	sort(answer.begin(), answer.end()); // 결과 출력
	cout << answer.size() << '\n';
	for (unsigned int i = 0; i < answer.size(); i++)
		cout << answer[i] << ' ';
	cout << '\n';


	return 0;
}

 

잘 풀린다.