[BOJ] 2583 영역 구하기

알고리즘

1. 직사각형를 좌표를 받아서 배열에 그려주기 
2. dfs 탐색 할때마다 탐색 횟수를 저장
3. 2.에서 저장된 탐색 횟수를 오름차순 후 출력

코드

#include <bits/stdc++.h>
using namespace std;
int m, n, k, _x1, _y1, _x2, _y2, cnt;
int a[101][101];
const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
bool visited[101][101];
vector <int> ret;

int dfs(int y, int x){
	visited[y][x] = 1;
    int ret = 1;
	for(int i = 0 ; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if( nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
		if(!visited[ny][nx] && a[ny][nx] == 0) ret += dfs(ny,nx) ;
	}
	return ret;
}
int main(){
	cin >> m >> n >> k;
	
	for(int i = 0 ; i < k ; i++){
		cin >> _x1 >> _y1 >> _x2 >> _y2;
		for(int j = _x1; j < _x2 ; j++ ){
			for(int t = _y1; t < _y2; t++ ){
				a[t][j] = 1;
			}
		}
	}
	
	for(int i = 0 ; i < m; i ++){
		for(int j = 0; j < n ; j++){
			if(!visited[i][j] && a[i][j] == 0){
				ret.push_back(dfs(i,j));
			}
		}
	}
	
	sort(ret.begin(), ret.end());
	
	cout << ret.size() << '\n';
	for(int r: ret){
		cout << r << ' ';
	}

}

정리

• 정사각형의 좌표 두개가 주어지면 반복문을 활용하여 표현이 가능
• dfs 함수의 리턴을 int형으로 하여 탐색한 깊이를 알수 있음

느낀점

• 배열은 중고등학교 때 배운 x축  y축과는 다른 x축 -y축이다. 이부분에 헷갈리지 않도록 지속적이 훈련이 필요하다.