[C++] 방의 크기 구하기

숙제 3 (방 크기)

★ STACK 사용

---

이와같이건물의평면도가주어졌을때, 이건물내부에있는방의개수와각방의크기를구하는프로그램을작성하시오. 각방의크기는위의예에서와같이가로, 세로 한 칸으로 만들어진 공간의 개수를 나타내며, 오른쪽에서 각숫자를나타내는문자의개수와일치한다. 따라서, 위의 건물에는 8 개의 방이 있으며, 각 방의 크기는 1번방부터 8번방까지 각 각 차례로 53, 13, 6, 42, 4, 57, 2, 35이다.

 

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


int main(){
	stack<int> s1;  //x좌표 저장
	stack<int> s2; //y좌표 저장
	stack<int> dir; //dir 저장
	int num[100]={0x00,};
	int row,col;
	cin>>row>>col;
	char **arr;
	int n=0x00;

	int direction[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
	int d=0x00;
	int inx=0x00;
	int iny=0x00;
	int x,y;
	arr=new char*[col];
	for(int i=0;i<col;i++) arr[i]=new char[row+1];
	for(int i=0;i<col;i++){
		for(int j=0;j<row;j++) cin>>arr[i][j];}
	for(int i=1;i<col-1;i++){
		for(int j=1;j<row-1;j++){
			if(arr[i][j]!='.') continue;
			arr[i][j]='x';
			num[n]++;
			s1.push(i);
			s2.push(j);
			dir.push(0);
			while(!(s1.empty())){
				x=s1.top();
				y=s2.top();
				d=dir.top();
				s1.pop();
				s2.pop();
				d=0;
				while(d<4){
					inx=x+direction[d][0];
					iny=y+direction[d][1];
					if(arr[inx][iny]=='.'){
						num[n]++;
						arr[inx][iny]='x'; //이미 방이 포함되었다는 걸 x로
						s1.push(inx);
						s2.push(iny);
						
					}
					d++;
					
				}
			
			}
			n++;
			
		}
	}
	sort(num, num+100);
	cout<<n<<endl;
	for(int i=99;num[i]!=0&&num[i]>=0;i--) cout<<num[i]<<" ";
	cout<<endl;
	for(int i=0;i<col;i++) delete[] arr[i];
	delete[] arr;
	
	return 0;
}