알고리즘 공부

장애물 인식 프로그램

컴퓨터과학 2023. 3. 2. 20:07

https://softeer.ai/practice/info.do?idx=1&eid=409 

 

Softeer

연습문제를 담을 Set을 선택해주세요. 취소 확인

softeer.ai

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
struct Pro{
 int index;
 bool bCheck;
};
int maxBlock;
int gCount=1;
 vector<int> sizesave;
vector<int>line;
map<int,int>savemap;
void Print(vector<vector<Pro>> map,int N){
	for(int i=0;i<N;i++){
	     for(int j=0;j<N;j++){
			 if(map[i][j].index!=0){
				 map[i][j].index=map[i][j].index;
				  maxBlock=map[i][j].index;
				  savemap[map[i][j].index]++;
			 }else{
			 }
		 }
	}
}
bool dfs(vector<vector<Pro>> &map,int x,int y, int c){
	if(x<=-1||y<=-1||x>=map.size()||y>=map.size()){	
		return false;
	}
	if(map[x][y].bCheck==false&&map[x][y].index==1){
		map[x][y].bCheck=true;
		map[x][y].index=c;
		
		dfs(map,x,y+1,c);
		dfs(map,x+1,y,c);
	    dfs(map,x-1,y,c);
		dfs(map,x,y-1,c);
		return true;
	}	
	return false;
}

int main(int argc, char** argv)
{
	//자율 주행팀 sw 엔지니언인 당신에게 장애물과 도로를 인식할수 있는 프로그램을 만들라는 업무가 주어짐
	/*
	  그림1 정사각형 모양의 지도가 있다.
	  1은 장애물 0은 도로가 잇는곳을 뜻함
	*/
    int N;
	cin>>N;
	vector<vector<Pro>> map;
	for(int i=0;i<N;i++){
		vector<Pro> tmpMaps;
		string tmp;
		cin>>tmp;
		for(int j=0;j<N;j++){
			Pro pro;
			pro.index=tmp[j]- '0';
			pro.bCheck=false;
			tmpMaps.push_back(pro);
		}
		map.push_back(tmpMaps);
	}

	int result=0;
    int counts=1;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			bool bCheck=dfs( map,i,j,counts);
			if(bCheck==true){
				counts++;
				result++;
			}	
		}	
	}

	sort(line.begin(),line.end());
	
	for(auto it=savemap.begin();it!=savemap.end();it++){
		sizesave.push_back(it->second);
	}
	
	sort(sizesave.begin(),sizesave.end());
	if(sizesave.size()>0){
	for(int i=0;i<sizesave.size()-1;i++){
		cout<<sizesave[i]<<endl;
	}
	cout<<sizesave[sizesave.size()-1];
	}
	return 0;