2583 - 영역 구하기

문제

코드

#include <bits/stdc++.h>
using namespace std;
int x,y,k,lx,ly,rx,ry,n,m; 
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int visited[104][104];
int arr[104][104];
vector<int> ret;

int dfs(int y, int x){
	visited[y][x] = 1;
	int ret = 1;
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
		if(!visited[ny][nx] && !arr[ny][nx]) 
		ret += dfs(ny, nx);
	}
	return ret;
}


int main(){
	cin >> m >> n >> k;
	
	while(k--){
		cin >> lx >> ly >> rx >> ry;
	for(int i = lx; i < rx; i++){
		for(int j = ly; j < ry; j++){
			arr[j][i] = 1;
		}
	}
}
	
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(arr[i][j] != 1 && visited[i][j] ==0){
				ret.push_back(dfs(i,j));
			}
		}
	}
	
	sort(ret.begin(), ret.end());
	cout << ret.size() << '\n';
	for(int a : ret) cout << a << " ";
	return 0;
}

풀이 과정

dfs 함수의 반환 값을 int형으로 해두었으니 반환 값을 vector에 담아서 size를 출력하면 connected component의 갯수가 되고, 이를 정렬해서 출력하면 넓이가 된다.

결과

후기

사실 실버 1이라기에 너무 어려웠다. 넓이를 구하는 아이디어가 안떠올랐는데 탐색에 대한 큰 흐름을 잘못 이해한것 같기도 해서 조금 아쉬웠다. 응용되도 풀 수 있도록 기초를 잘 알고 있는게 중요한듯 하다.