알고리즘 공부
장애물 인식 프로그램
컴퓨터과학
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;