2583. 영역 구하기

추천도 : 3 (풀어볼만한 문제이다.)

이 문제의 경우 전체탐색의 문제이다. 간단한 문제인거 같지만, 함정이 있어 조심해야된다. 

함정은

1.  데이터 그대로 인덱스로 사용하면 의도한 그림이 나오지 않는다. 이럴 경우, 1 6 14라는 답을 얻게된다.
2.  n m 를 행/열이라고 생각하여 사용하면 그림은 행/열이 바껴서 그려진다.

이것만 유의하면 손쉽게 풀 수 있는 문제이다. 

만약 이 문제가 단순히 직사각형을 제외한 면적을 구하는 문제였다면, 굳이 100*100 배열을 선언하여 공간을 낭비하지 않을 수 있다. 직사각형의 정보를 받을 때, 면적을 계산하고 겹치는 부분이 있다면, 그 공간의 면접만 빼줘 직사각형의 모든 넓이를 구할 수 있다. 이를 전체면적에서 빼면 간단하게 짧은 시간에 구할 수 있다. 

 

저는 map을 전체 탐색을 하면 BFS를 이용해서 동일한 공간을 계산해주었습니다.

 

 

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


int map[110][110] = { 0 };
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int n, m, k;
vector<int> list;
void checking(int i, int j,int count) {
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] <m && j + dy[k] >= 0 && j + dy[k] <n) {
			if (map[i + dx[k]][j + dy[k]] == 0) {
				list[count]++;
				map[i + dx[k]][j + dy[k]] = count;
				checking(i + dx[k], j + dy[k], count);
			}
		}
	}
}

int main() {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int k = x1; k <= x2-1; k++) {
			for (int kk = y1; kk <= y2-1; kk++) {
				map[k][kk] = -1;
			}
		}
	}

	list.push_back(0);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				list.push_back(1);
				map[i][j] = list.size() - 1;
				checking(i, j, list.size()-1);
			}
		}
	}
	cout << list.size()-1 << endl;
	sort(list.begin(), list.end());
	for (int i = 1; i < list.size(); i++)
		cout << list[i] << " ";

	return 0;

}

 

 

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

2583번: 영역 구하기