BOJ - 단지번호 붙이기(2667)

실버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;
}
 

Reference

• 백준(2667번) - 단지번호붙이기