백준 : 16234 *

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

16234번: 인구 이동

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
 
int A[51][51];
int N,L,R;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
bool chk = true;
 
void BFS(){
    bool check[51][51]={false,};
    
    chk =false;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(check[i][j]==true) continue;
            queue <pair<int,int>> q;
            q.push({i,j});
            int q_y,q_x;
            queue <pair<int,int>> set_q;
            int sum=0;
            int cnt=0;
            check[i][j] =true;
            while(!q.empty()){
                q_y = q.front().first;
                q_x = q.front().second;
                q.pop();
                set_q.push({q_y,q_x});
               // cout<<"y : "<<q_y<<" x :"<<q_x<<endl;
                sum += A[q_y][q_x];
                ++cnt;
                for(int k=0;k<4;k++){
                    int ny = q_y + dy[k];
                    int nx = q_x + dx[k];
                    
 
                    if(ny>N||ny<1||nx>N||nx<1) continue;
                    if(check[ny][nx]) continue;
                    int abs_value = abs(A[ny][nx] - A[q_y][q_x]);
                    if(!(abs_value<=R && abs_value>=L)) continue;
                    check[ny][nx] = true;
                    q.push({ny,nx});
                    chk = true;
                }
            }
            //cout<<"sum : "<<sum<<endl;
            //cout<<"cnt : "<<cnt<<endl;
            sum = sum/cnt;
 
            while(!set_q.empty()){
                q_y = set_q.front().first;
                q_x = set_q.front().second;
                set_q.pop();
                A[q_y][q_x] = sum;
            }
        }
    }
    
}
 
int main(void){
 
    cin>>N>>L>>R;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>A[i][j];
        }
    }
    
    int cnt=0;
    chk = true;
    while(chk){
        ++cnt;
        BFS();
 
    }
 
    cout<<cnt-1;
 
}