[백준] 실버1-영역 구하기 C++ 2583번

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

 

// 범위 잘 생각하기, y1 변수 사용 시 #define 걸기

1. 전역변수 사용한 답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define y1 aaaa
int M, N, K;
int x1, x2, y1, y2;
int area, cnt;
vector<int> areas;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
bool visited[100][100];
int adj[100][100];

void dfs(int y, int x)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (adj[ny][nx]) continue;
		if (visited[ny][nx]) continue;

		area++;
		dfs(ny, nx);
	}
}

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

	cin >> M >> N >> K;

	for (int i = 0; i < K; i++)
	{
		cin >> x1 >> y1;
		cin >> x2 >> y2;

		for (int i = y1; i < y2; i++)
		{
			for (int j = x1; j < x2; j++)
			{
				adj[i][j] = 1;
			}
		}
	}
	
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!adj[i][j] && !visited[i][j])
			{
				area = 1;
				dfs(i, j);
				areas.push_back(area);
				cnt++;
			}
		}
	}
	cout << cnt << '\n';
	sort(areas.begin(), areas.end());
	for (int i : areas)
		cout << i << ' ';

	return 0;
}

 

2. 전역변수 안쓰고 dfs 결과값을 활용한 답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define y1 aaaa
int M, N, K;
int x1, x2, y1, y2;
vector<int> areas;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
bool visited[100][100];
int adj[100][100];

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 (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (adj[ny][nx]) continue;
		if (visited[ny][nx]) continue;

		ret += dfs(ny, nx);
	}
	return ret;
}

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

	cin >> M >> N >> K;

	for (int i = 0; i < K; i++)
	{
		cin >> x1 >> y1;
		cin >> x2 >> y2;

		for (int i = y1; i < y2; i++)
		{
			for (int j = x1; j < x2; j++)
			{
				adj[i][j] = 1;
			}
		}
	}
	
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!adj[i][j] && !visited[i][j])
			{
				areas.push_back(dfs(i, j));
			}
		}
	}
	cout << areas.size() << '\n';
	sort(areas.begin(), areas.end());
	for (int i : areas)
		cout << i << ' ';

	return 0;
}