[softeer/C++] 장애물 인식 프로그램

장애물 인식 프로그램

1은 장애물, 0은 도로
연결선(좌우, 위아래) 장애물들의 모임인 블록을 정의 후 번호를 붙임
출력 - 장애물 블록 수 출력, 각 블록에 속한는 장애물 수를 오름차순으로 출력

BFS

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int N;

int map[26][26];
int visited[26][26];

vector<int> number;
struct info{
	int x, y;
};

int func(int x, int y){

	queue<info> q;
	q.push({x, y});

	int cnt=1;
	visited[x][y]=1;

	while(!q.empty()){
		info temp = q.front();
		q.pop();

		for(int i=0;i<4;i++){
			int nx = temp.x + dx[i];
			int ny = temp.y + dy[i];

			if(nx>=0 && ny>=0 && nx<N && ny<N){
				if(map[nx][ny]==1&&visited[nx][ny]==0){
					visited[nx][ny]=1;
					q.push({nx, ny});
					cnt++;
				}
			}
		}
	}
	return cnt;
}



int main(int argc, char** argv)
{
	cin >> N;
	string input;
	
	for(int i=0;i<N;i++){
		cin >> input;
		for(int j=0 ; j<N;j++){
			map[i][j] = input[j]-'0';
		}
	}
 	
	for(int i=0;i<N;i++){
		for(int j=0 ; j<N;j++){
			if(map[i][j]==1&&visited[i][j]==0){
				number.push_back(func(i, j));
			}
		}
	}

	cout<<number.size()<<"\n";
	sort(number.begin(), number.end());

	for(int i=0;i<number.size();i++){
		cout <<number[i]<<"\n";
	}


	return 0;
}

DFS

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int N;

int map[26][26];
int visited[26][26];

vector<int> number;
struct info{
	int x, y;
};

int func(int x, int y){
	int cnt=1;
	visited[x][y]=1;

	for(int i=0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];

		if(nx>=0 && ny>=0 && nx<N && ny<N){
			if(map[nx][ny]==1&&visited[nx][ny]==0){
				cnt+=func(nx, ny);
			}
		}
	}
	return cnt;
}



int main(int argc, char** argv)
{
	cin >> N;
	string input;
	
	for(int i=0;i<N;i++){
		cin >> input;
		for(int j=0 ; j<N;j++){
			map[i][j] = input[j]-'0';
		}
	}
 	
	for(int i=0;i<N;i++){
		for(int j=0 ; j<N;j++){
			if(map[i][j]==1&&visited[i][j]==0){
				number.push_back(func(i, j));
			}
		}
	}

	cout<<number.size()<<"\n";
	sort(number.begin(), number.end());

	for(int i=0;i<number.size();i++){
		cout <<number[i]<<"\n";
	}


	return 0;
}