[백준 2583번] 영역 구하기 (C++)

문제링크 : https://www.acmicpc.net/problem/2583

#include <bits/stdc++.h> 
using namespace std;

int area[100][100];
int n, m, k, cnt = 0, cnt2 = 0;
int x1, x2, y11, y2;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>>q;
vector<int> v;

void bfs(int x, int y)
{
	area[x][y] = 1;
	q.push({ x,y });
	while (!q.empty())
	{
		int yy = q.front().first, xx = q.front().second; q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = xx + dx[i];    //다음 x 값
			int ny = yy + dy[i];    //다음 y 값
			if (nx < 0 || ny < 0 || nx >=n || ny >=m) { continue; }  //범위 조건
			if (!area[ny][nx])      //직사각형 영역이 아니라면
			{
				area[ny][nx] = 1;   //방문 처리 (직사각형 영역과 동일값으로)
				q.push({ ny,nx });  //연결된 값 탐색
				cnt++;              //영역 카운트 증가
			}
		}
	}	
}

int main()
{
	cin >> m >> n >> k;
	while (k--)
	{
		cin >> x1 >> y11 >> x2 >> y2;
		for (int i = y11; i < y2; i++)
		{
			for (int j = x1; j < x2; j++)
			{
				area[i][j] = 1;  //직사각형 영역은 1로 초기화
			}
		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!area[i][j] )  //직사각형 영역이 아니라면
			{
				cnt = 1;
				bfs(i, j);
				v.push_back(cnt);  //bfs 탐색후 cnt 값 대입
				cnt2++;            //영역의 갯수
			}
		}
	}
	
	cout << cnt2 << "\n";
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	return 0;
}

한번의 좌표당 한번의 탐색이 아닌, 각 테스트케이스(좌표) 전부 입력 받고 1로 초기화 해준 후에 bfs 탐색 시작한다.

ny, nx 위치가 바뀌지 않도록 주의해야 한다.