인구 이동

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 12:02 ~ 12:27
int N, L, R, ans;
int board[55][55];
int vis[55][55];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> L >> R;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    while(true)
    {
        // BFS를 돌면서 인구수를 비교해서 L이상 R이하면 큐에 넣자
        bool flag = false;
        for(int i=0;i<N;i++)
            fill(vis[i], vis[i]+N, false);
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(vis[i][j]) continue;
                queue<pair<int,int>> q;
                vector<pair<int,int>> change;
                q.push({i,j});
                change.push_back({i,j});
                vis[i][j] = true;
                int sum=board[i][j];
                while(!q.empty())
                {
                    auto cur = q.front(); q.pop();
                    for(int dir=0;dir<4;dir++)
                    {
                        int ny = cur.first + dy[dir];
                        int nx = cur.second + dx[dir];
                        if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
                        int diff = abs(board[cur.first][cur.second] - board[ny][nx]);
                        if(vis[ny][nx] or diff<L or diff >R) continue;
                        q.push({ny,nx});
                        vis[ny][nx] = true;
                        sum += board[ny][nx];
                        change.push_back({ny,nx});
                    }
                }
                /* 이동이 있었다면 끝내면 안됨 */
                if(change.size() >= 2) flag = true;
                int avg = sum/change.size();
                for(int j=0;j<change.size();j++)
                {
                    auto cur = change[j];
                    board[cur.first][cur.second] = avg;
                }
            }
        }
        /* 이동한 나라가 없으므로 종료 */
        if(!flag) break;
        ans++;
    }
    cout << ans;
    return 0;
}

• 로직
  • 모든 점에 대해서 BFS 수행
  • BFS를 돌면서 인접한 점과 인구수 차이가 L 이상 R이하이면 큐에넣고 계속 수행
  • 인구 이동이 없으면 종료