백준 2583 c++ -[PlusUltraCode]

[필자 사고]

전형적인 2차원 배열 그래프 탐색문제이다

이 문제의 특이한 점은 좌표로 되어 있다는 것이다.

index로만 배열을 다뤄온지라 좌표를 보고 몇십분간 어떻게 해야 오류가 안날지 계쏙 생각하게 되었다.

간단하게 문제 해결방법을 말하겠다.

 

1. 문제에서 주어지는 빗금친 영역을 배열에 -1로 표시해줬다.

2. 나머지 빗금치지 않은 부분을 BFS탐색을 이용해 넓이를 Resultcount벡터에 넣어줬다.

 

[소스코드]

 

 

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

typedef struct Rect {
	int x1, y1, x2, y2;

}Rect;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int N, M, K;
vector<vector<int>> Arr;
vector<vector<bool>> visited;
vector<Rect> RectPoint;
vector<int> ResultCount;
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void PaintArr() {
	for (int i = 0; i < RectPoint.size(); i++) {
		for (int sero = RectPoint[i].y1; sero < RectPoint[i].y2; sero++) {
			for (int garo = RectPoint[i].x1; garo < RectPoint[i].x2; garo++) {
				Arr[sero][garo] = -1;
			}
		}
	}
}

void Input() {
	cin >> N >> M >> K;
	Arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M,1);
		visited[i].resize(M);
	}
	RectPoint.resize(K);

	
	for (int i = 0; i < K; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		RectPoint[i].x1 = a;
		RectPoint[i].y1 = b;
		RectPoint[i].x2 = c;
		RectPoint[i].y2 = d;
	}
	
	PaintArr();
	
}
void Print() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cout << Arr[i][k] << "  ";
		}
		cout << '\n';
	}
}
void BFS() {
	queue<pair<int, int>> myQueue;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k] == 1&&visited[i][k]==false) {
			
				myQueue.push({ i,k });
				visited[i][k] = true;
				int area = 1;
				while (!myQueue.empty()) {
					int nowSero = myQueue.front().first;
					int nowGaro = myQueue.front().second;
					myQueue.pop();
					for (int adj = 0; adj < 4; adj++) {
						int nextSero = nowSero + dy[adj];
						int nextGaro = nowGaro + dx[adj];
						if (Inside(nextSero, nextGaro) &&
							Arr[nextSero][nextGaro] == 1 &&
							visited[nextSero][nextGaro] == false) {
							visited[nextSero][nextGaro] = true;
							myQueue.push({ nextSero,nextGaro });
							area++;
						}
					}
				}
				ResultCount.push_back(area);

			}
		}
	}
}

int main(void) {
	Input();
	BFS();
	cout << ResultCount.size()<<"\n";
	sort(ResultCount.begin(), ResultCount.end());
	for (int temp : ResultCount) {
		cout << temp << " ";
	}
}