이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 86 번째 글 입니다.
목차
실버1 : DFS 문제이다.
Code
#include <iostream>
#include <vector>
#include <typeinfo>
#include <algorithm>
using namespace std;
int n;
int map[26][26];
bool isVisit[26][26] = {0,};
vector<int> num;
int apart = 0;
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
bool compare(int i, int j) {return i < j;}
void go(int now_y, int now_x, int apart, int &count){
if (isVisit[now_y][now_x] || map[now_y][now_x] == 0) return;
isVisit[now_y][now_x] = true;
map[now_y][now_x] = apart;
count++;
for (int i = 0 ; i < 4; i++) {
int next_y = now_y + dy[i];
int next_x = now_x + dx[i];
if (0 <= next_y && next_y < n && 0 <= next_x && next_x < n) {
go(next_y, next_x, apart, count);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cin >> n;
for (int i = 0; i < n; i++) {
char a[26];
cin >> a;
for (int j = 0; j < n; j++) {
map[i][j] = a[j] - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0 || isVisit[i][j] == true) continue;
apart++;
int count = 0;
go(i, j, apart, count);
num.push_back(count);
}
}
sort(num.begin(), num.end(), compare);
cout << apart << '\n';
for (int i = 0; i < int(num.size()); i++) {
cout << num[i] << '\n';
}
return 0;
}