2583번: 영역 구하기

Memo

어려웠던 부분

• x, y 표현이 평소에 구현하던 것과 달라서 어려웠습니다.
• 좌표 문제를 많이 접하지 않았던 탓에, 이차원 배열로 표현하는 것이 조금 어색했습니다.

전반적으로 기존에 풀던 문제들과 조금씩 다른 부분들이 있어서 푸는데 시간이 조금 걸린 문제였습니다. 다양한 문제들을 접해야 하는 이유가 바로 이런 부분 때문이 아닌가 생각이 듭니다.

Code

제출 날짜

2021/03/30

메모리

2060 KB

시간

0 ms

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define endl "\\n"
int M, N, K;
int g_map[102][102];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
std::queue<std::pair<int, int> >q;
std::vector<int> ans;
int numbers;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int x1, y1, x2, y2;

	input_faster();
	std::cin >> M >> N >> K;
	for (int i = 0 ; i < K ; i++)
	{
		std::cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1 ; x < x2 ; x++)
			for (int y = y1 ; y < y2 ; y++)
				g_map[x][y] = 1;
	}
}

void bfs(int i, int j)
{
	int y, x, ny, nx;
	int area = 0;

	if (g_map[i][j])
		return ;
	numbers++;
	q.push({i, j});
	g_map[i][j] = 1;
	while(!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();
		area++;
		for (int k = 0 ; k < 4; k++)
		{
			nx = x + dx[k];
			ny = y + dy[k];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M || g_map[nx][ny])
				continue;
			g_map[nx][ny] = 1;
			q.push({nx, ny});
		}
	}
	ans.push_back(area);
}

void solve()
{
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < M ; j++)
		{
			bfs(i, j);
		}
	}
}

void print_val()
{
	std::cout << numbers << endl;
	std::sort(ans.begin(), ans.end());
	for(size_t i = 0 ; i < ans.size() ; i++)
		std::cout << ans[i] << " ";
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}