[Silver I] 영역 구하기 - 2583

[Silver I] 영역 구하기 - 2583

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

DFS를 활용해서 연결된 컴포넌트 그룹을 카운팅 하고 그룹의 합을 구하는 문제였습니다.

기존에 사용하던 void DFS()로는 각  그룹을 카운팅 하는데 문제가 있어서 조금 어려워하고 있다가

강사님의 설명을 듣고 생각을 바꾸게 되었습니다.

int DFS()로 변경해서 한번 연결된 컴포넌트 그룹을 탈출하면 해당 카운트를 알 수 있도록 문제를 해결했습니다. 

[Silver I] 영역 구하기 - 2583 풀이코드

#include <bits/stdc++.h>
using namespace std;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int m, n, k, nx, ny, a[104][104], visited[104][104], leftX, leftY, rightX, rightY, ret;
vector<int> retV;

int dfs(int y, int x)
{
	visited[y][x] = 1;
	int ret = 1;	
	for(int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;
		if (a[ny][nx] == 0 && !visited[ny][nx]) 
		{
			ret += dfs(ny, nx); 
		}
	}
	
	return ret;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> m >> n >> k;
	
	vector<int> retV;
	
	for (int cnt = 0; cnt < k; cnt++)
	{
		cin >> leftX >> leftY >> rightX >> rightY;
		for (int i = leftY; i < rightY; i++)
		{
			for (int j = leftX; j < rightX; j++)
			{
				a[i][j] = 1;
			}
		}
	}
	
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[i][j] == 0 && !visited[i][j])
			{
				retV.push_back(dfs(i, j));
			}
		}
	}
	sort(retV.begin(), retV.end());
	cout << retV.size() << '\n';
	for (int i : retV) cout << i << " ";
	return 0;
}