[BFS] 백준 2583 영역 구하기

www.acmicpc.net/problem/2583

2583번: 영역 구하기

수행 시간 : 1시간

 

난이도에 비해 상당히 까다로웠던 문제. 우리가 아는 배열이나 벡터는 좌표가 아래로 뻗어나가는데 문제에서는 위로 뻗어나가고 그것도 모눈종이라서 좌표가 하나씩 밀리므로 새로운 temp 벡터를 선언하여 bfs를 돌린 값을 저장시키는 방식으로 구현하였다. 

 

 

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

int n, m, k;
int left_x, left_y, right_x, right_y;
//vector<vector<int>> v_map;
int v_map[101][101];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool visited[101][101];
int area_cnt[101];
int area_size = 0;

int bfs(int a, int b) {
	int cnt = 0;
	queue<pair<int, int>> q;
	visited[a][b] = true;
	cnt++;
	q.push( { a,b } );
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (visited[nx][ny] == false && v_map[nx][ny] == 0) {
					visited[nx][ny] = true;
					q.push({ nx,ny });
					cnt++;
				}
			}
		}
	}
	return cnt;
}

void make_map() {
	for (int i = left_y ; i < right_y;i++) {  
		for (int j = left_x ; j < right_x;j++) {
			v_map[i][j] = 1;
		}
	}
}

int main() {
	vector<int> temp;
	cin >> n >> m >> k;
	for (int i = 0;i < k;i++) {
		cin >> left_x >> left_y >> right_x >> right_y;
		make_map();
	}
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < m;j++) {
			if (v_map[i][j] == 0 && visited[i][j] == false) {
				temp.push_back(bfs(i, j));
			}
		}
	}
	sort(temp.begin(), temp.end());
	int size = temp.size();
	cout << size << "\n";
	for (int i = 0;i < size;i++) {
		cout << temp[i] << " ";
	}
}