2667 단지 번호 붙이기

DFS나 BFS를 통한 브루트포스..

DFS로 풀기

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;

int num;
int apart[25][25];
int visited[25][25];
int direction[4][2] = {
    {0, -1}, {1,0},
    {0, 1}, {-1, 0}
};

void countDanji(int r, int c, bool &isFirst, vector<int>& count) {
    if(apart[r][c] == 0 || r >= num || c>= num || r<0 || c<0|| visited[r][c]) {
        return;
    }

    visited[r][c] = true;
    if(isFirst) {
        isFirst = false;
        count.push_back(1);
    } else {
        int index = (int) count.size() - 1;
        count[index] += 1;
    }

    for(int i= 0; i<4; i++) {
        int nextRow = r + direction[i][0];
        int nextCol = c + direction[i][1];
        countDanji(nextRow, nextCol, isFirst, count);
    }
}

int main(int argc, const char * argv[]) {
    cin>>num;
    vector <int> count;
    cin.ignore();
    for(int i = 0; i<num; i++) {
        fill_n(visited[i], num, false);
    }


    for(int i = 0; i<num; i++) {
        for(int j = 0; j<num; j++) {
            int temp;
            scanf("%1d", &temp);
            apart[i][j] = temp;
        }
    }

    for(int i = 0; i<num; i++) {
        for(int j = 0; j<num; j++) {
            bool isFirst = true;
            countDanji(i, j, isFirst, count);
        }
    }

    int size = (int) count.size();
    cout<<size<<endl;

    sort(count.begin(), count.end());

    for(int i = 0; i<size; i++) {
        cout<<count[i]<<endl;
    }

    return 0;
}

BFS로 풀기

int num;
int apart[25][25];
int direction[4][2] = {
    {0, -1}, {1,0},
    {0, 1}, {-1, 0}
};

int danji[25][25];
int ans[25*25];

void bfs(int r, int c, int &cnt) {
    if(apart[r][c] == 0 || danji[r][c] != 0) {
        return;
    }
    queue <pair<int, int>> q;

    q.push(make_pair(r, c));
    cnt += 1;
    danji[r][c] = cnt;

    while(!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;

        q.pop();

        for(int i = 0; i<4; i++) {
            int nextR = row + direction[i][0];
            int nextC = col + direction[i][1];

            if(nextR < num && nextR >= 0 && nextC < num && nextC >= 0 && apart[nextR][nextC] == 1 && danji[nextR][nextC] == 0) {
                q.push(make_pair(nextR, nextC));
                danji[nextR][nextC] = cnt;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin>>num;
    vector <int> count;
    cin.ignore();
    for(int i = 0; i<num; i++) {
        fill_n(visited[i], num, false);
    }


    for(int i = 0; i<num; i++) {
        for(int j = 0; j<num; j++) {
            int temp;
            scanf("%1d", &temp);
            apart[i][j] = temp;
        }
    }
    int cnt = 0;
    for(int i = 0; i<num; i++) {
        for(int j = 0; j<num; j++) {
            bfs(i, j, cnt);
        }
    }

    cout<<cnt<<endl;

    for(int i = 0; i<num; i++) {
        for(int j = 0; j<num; j++) {
            if(danji[i][j] != 0) {
                ans[danji[i][j]] += 1;
            }
        }
    }

    sort(ans + 1, ans + cnt + 1);

    for(int i = 1; i<=cnt; i++) {
        cout<<ans[i]<<endl;
    }