백준 2667번 : 단지번호붙이기 - bfs 기본문제 (c++)

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

2667번: 단지번호붙이기

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int map[30][30];
bool chk[30][30];
int cnt=0;

vector <int> solution;
vector <int> dy={-1,0,1,0};
vector <int> dx={0,1,0,-1};

void bfs(int y, int x){
    queue <pair<int, int>> q;
    q.push(make_pair(y,x));
    chk[y][x]=true;

    while(!q.empty()){
        pair<int, int> p;
        p = q.front();
        q.pop();
        cnt++;
        for(int i=0;i<4;i++){
            int ny = p.first+dy[i];
            int nx = p.second+dx[i];
            if(map[ny][nx]==1&&chk[ny][nx]==false){
                q.push(make_pair(ny,nx));
                chk[ny][nx]=true;
            }
        }
    }
}


int main(){

    freopen("input.txt","r",stdin);
    cin>>N;

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%1d", &map[i][j]);
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cnt=0;
            if(map[i][j]==1 && chk[i][j]==false){
                bfs(i, j);
                solution.push_back(cnt);
            }
        }
    }
    sort(solution.begin(),solution.end());

    cout<<solution.size()<<"\n";
    for(int i=0;i<solution.size();i++){
        cout << solution[i] <<"\n";
    }

    return 0;
}