백준 2667번 단지번호붙이기

https://www.acmicpc.net/problem/2667

기본적인 bfs 문제이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0;
char house[25][25] = {0, };
int bfs[25][25] = {0, };
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
bool isInner(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n);
}
int process(int x, int y, int num) {
    int ret = 1;
    bfs[x][y] = num;
    
    for(int i = 0 ; i < 4; ++i) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        
        if (isInner(newX, newY) && house[newX][newY] == '1' && bfs[newX][newY] != bfs[x][y] ) {
            ret += process(newX, newY, num);
        }
    }
    return ret;
}
int main()
{
    vector<int> v;
    int numOfGroup = 1;
    
    scanf("%d", &n);
    
    for(int i = 0 ; i < n; ++i) {
        scanf("%s", &house[i]);
    }
    
    for(int i = 0 ; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if (house[i][j] == '1' && bfs[i][j] == 0) {
                v.push_back(process(i, j, numOfGroup));
                numOfGroup++;
            }
        }
    }
    
    sort(v.begin(), v.end());
    
    printf("%d\n", numOfGroup - 1);
    for (vector<int>::size_type i = 0; i < v.size(); ++i) {
        cout << v[i] << endl;
    }
    
    return 0;
}