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

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

Softeer

---

전형적인 그래프 탐색 문제다.

dfs, bfs 문제를 안 푼 지 넘 오래됐어서 약간 버벅거렸다.

 

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

using namespace std;

int block[25][25];
int visited[25][25] = {0,};
int n; int c;

int dfs(int x, int y){
	if (x >= 0 && x < n && y >= 0 && y < n){
		if (visited[x][y] == 0 && block[x][y]==1){
			visited[x][y] = 1; c++;
			dfs(x-1,y);
			dfs(x,y-1);
			dfs(x+1,y);
			dfs(x,y+1);
			return c;
		}
	}
	return -1;
}

int main(int argc, char** argv)
{
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%1d", &block[i][j]);
		}
	}
	int cnt = 0, result;
	vector<int> v;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			c = 0; result = dfs(i,j);
			if (result > 0) {
				cnt++;
				v.push_back(result);
			}
		}
	}

	//결과 출력
	cout<<cnt<<"\n";
	sort(v.begin(), v.end());
	for(int i=0; i<cnt; i++){
		cout<<v[i]<<"\n";
	}

	return 0;
}

 

예전에 백준에 비슷한 문제가 있던 것 같아서 예전 기록을 다시 찾아봤는데, 그때는 bfs로 풀었었당