[백준 2667번 / C++] 단지번호붙이기

• bfs, dfs 자신있는 것으로 해보자. 
• main문에서 함수 호출할 때 증가하는 cnt는 영역을 표현. 
• 함수에서 또 함수를 호출할 때 증가하는 cnt는 영역안의 넓이를 표현. 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std; 
int n; 
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 
int map[25][25]; 
int visited[25][25]; 
int cnt1; 
void dfs(int y, int x) {
	cnt1++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; 
		int ny = y + dy[i]; 
		if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue; 
		if (map[ny][nx] == 0 || visited[ny][nx] == 1)continue; 
		visited[ny][nx] = 1; 
		dfs(ny, nx); 
	}
	return; 
}
int main() {
	cin >> n; 
	for (int i = 0; i < n; i++) {
		string s; cin >> s; 
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j]-'0'; 
		}
	}
	int cnt = 0; 
	vector <int> v; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] && !visited[i][j]) {
				visited[i][j] = 1;
				dfs(i, j); 
				
				v.push_back(cnt1); 
				cnt1 = 0; 		
				cnt++; 
			}
		}
	}
	cout << cnt << "\n"; 
	sort(v.begin(), v.end()); 
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl; 
	}
}

 

2667번: 단지번호붙이기