[C/C++] 백준 2583번 영역 구하기

 

문제 풀이

이 문제는 DFS로 풀 수 있는 문제이다.

 

(1) 문제에 좌측 아래가 (0,0)으로 주어져있다. 이 때 판단해야한다. 실제로 문제에 나온 좌표계로 맞출 것인지 아니면 맞출 필요가 없는지 판단해야한다.

(2) 해당 문제는 반전되어서 그대로 풀어도 상관이 없다. 영역 개수와 크기만 판단하면 된다.

(3) DFS로 문제를 풀었다. 영역 크기를 구하는 게 이 문제가 다른 문제와 좀 다른 부분이었다.

 

느낀점:

이러한 좌표 문제를 만났을 땐 행과 열이 헷갈리지 않도록 변수를 구성하는게 좋은 방법이라고 생각된다.

소스코드

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

int m,n,k;
int cnt;
int area_size;

int map[110][110];
int visit[110][110];

int a,b,c,d;

int dr[4]={0,0,-1,1};
int dc[4]={1,-1,0,0};

vector<int> v;

void dfs(int row, int col, int& local_cnt){
	visit[row][col]=1;
	local_cnt++;
	
	for(int i=0; i<4; i++){
		int newrow=row+dr[i];
		int newcol=col+dc[i];
		
		if(newrow<0 || newcol<0 || newrow>=m || newcol>=n){
			continue;
		}
		
		if(visit[newrow][newcol]){
			continue;
		}
		
		if(map[newrow][newcol]==0){
			dfs(newrow, newcol, local_cnt);
		}
	}
}

int main(void) {

	cin>>m>>n>>k;
	
	while(k-->0){
		
		cin>>a>>b>>c>>d;
		
		for(int y=b; y<d; y++){
			for(int x=a; x<c; x++){
				map[y][x]=1;
			}
		}
	}


	for(int r=0; r<m; r++){
		for(int c=0; c<n; c++){
			if((!visit[r][c])&&(map[r][c]==0)){
				int lcnt=0;
				dfs(r,c,lcnt);
				v.push_back(lcnt);
				cnt++;
			}
		}
	}

	cout<<cnt<<endl;
	sort(v.begin(),v.end());
	for(int i=0; i<v.size(); i++){
		cout<<v[i]<<" ";
	}
	

	    
	return 0;
}