백준 16234 인구 이동

문제 링크: https://www.acmicpc.net/problem/16234
문제 난이도: 골드 5
알고리즘: 구현,그래프이론,그래프탐색,너비우선탐색,시뮬레이션
문제풀이 idea: NxN의 모양으로 각 나라별 인구수가 입력으로 들어온다.
문제에서 국경선을 공유하는 나리의 인구차이가 L명이상,R명 이하라면 두 나라가 국경선을 오늘 하루 동안 연다고 되어있다. ->이 부분을 어느 한 나라를 기준으로 상하좌우에 있는 나라가 L명이상 R명이하라면 기준인 나라와 이동가능한 나라의 인구수를 더한다. 그리고 공유가능한 나라의 수를 세어 합한 인구수/공유가능한 나라의 수
의 값이 국경선읠 공유한 각 나라의 인구수가 된다.
방문여부를 확인하는 vis배열과 인구수를 저장하는 arr배열 그리고 while문의 탈출조건으로 사용될 bool 변수 ch를 사용했다.
ch는 매번 인구이동이 가능할 경우 true로 값을 변경하고, 인구이동이 불가능할 경우 false로 값을 유지해 while의 탈출조건이 된다.

해결 코드:

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

using namespace std;

//입력으로 주어지는 값
int n,l,r;
//인구수 저장 배열
int arr[51][51];
//인구이동 가능 유무 판단
bool ch=false;
//중복 방문 방지 체크배열
int vis[51][51];
//상하좌우 방향값
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};


//매번 초기화를 위한 함수
void init(){
    ch=false;
    for(int i=0;i<n;i++){
        fill(vis[i], vis[i]+51, 0);
    }
}

//인구 이동이 가능한 나라를 찾기위해 bfs 사용
void bfs(int a,int b){
    vis[a][b]=1;
    queue<pair<int, int>>q;
    //인구이동이 가능한 나라 좌표를 저장 
    queue<pair<int, int>>lis;
    q.push({a,b});
    
    int sum=0;
    int cnt=0;
    while(!q.empty()){
        
        int x=q.front().first;
        int y=q.front().second;
        lis.push({x,y});
        sum+=arr[x][y];
        cnt++;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<n&&abs(arr[x][y]-arr[nx][ny])>=l&&abs(arr[x][y]-arr[nx][ny])<=r){
                ch=true;
                if(vis[nx][ny]==0){
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
        }
    }
    
    int val=sum/cnt;
    while(!lis.empty()){
        int x=lis.front().first;
        int y=lis.front().second;
        lis.pop();
        arr[x][y]=val;
    }
    
    
    
    
}



int main(){
    
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    int res=0;
    queue<pair<int, int>>q;
    cin>>n>>l>>r;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
    }
    
    while(1)
    {
        
        //매번 각 나라를 기준으로 bfs를 돌림
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(vis[i][j]==0){
                    bfs(i,j);
                }
            }
        }
        
        if(ch==false){
            break;
        }
        init();
        res++;
        
        
        
        
        
        
    }
    
    
    cout<<res<<"\n";
    
    
    
    return 0;
}