[C++] 백준 2583 : 영역 구하기

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

using namespace std;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1, 0,-1 };
int M, N, K;
vector<int> answer;

void bfs(vector < vector<int>>&G,int ci, int cj) {
	vector < vector<int> >Q;
	int cnt = 0;
	Q.push_back({ ci,cj });
	G[ci][cj] = 1;
	while (!Q.empty()) {
		ci = Q.front()[0];
		cj = Q.front()[1];
		cnt++;
		Q.erase(Q.begin());
		for (int d = 0; d < 4; d++) {
			int ni = ci + dx[d];
			int nj = cj + dy[d];
			if (0 <= ni && ni < M && 0 <= nj && nj < N && !G[ni][nj]) {
				Q.push_back({ ni,nj });
				G[ni][nj] = 1;
			}
		}
	}
	answer.push_back(cnt);
}

int main() {

	cin >> M >> N >> K;
	vector < vector<int>> G (M, vector<int>(N, 0));


	//직사각형 정보를 2차원 배열에 입력
	for (int k = 0; k<K; k++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = x1; j < x2; j++) {
			for (int i = y1; i < y2; i++) {
				G[i][j] = 1;
			}
		}
	}


	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (!G[i][j]) {
				bfs(G,i,j);
			}
		}
	}
	

	sort(answer.begin(), answer.end());
	cout << answer.size() << '\n';
	for (int num : answer) {
		cout << num << ' ';
	}


}

문제에서 좌표평면이 좌측하단에서 시작하고 가로가 x축, 세로가 y축인 형태여서, 좌상단에서 시작하는 좌표계를 생각하고 구현하면 인덱스 초과가 난다. 

 

enqueue 연산에 조건을 걸때 N과 M을 헷갈리지 말자