[BOJ 16234] 인구 이동

백준 :: BOJ :: 16234 :: 인구 이동

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

#include <bits/stdc++.h>

using namespace std;

struct A { int a, b; };

int N, L, R, f, sum, ans,

arr[50][50], dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

bool vi[50][50];

queue<A> q; vector<A> v;

inline bool check(int i, int j) { return (i >= 0 && j >= 0 && i < N&&j < N) ? true : false; }

inline bool cal(int a, int b) { return (abs(a - b) >= L && abs(a - b) <= R) ? true : false; }

void bfs() {

while (!q.empty()) {

auto tmp = q.front(); q.pop();

for (int d = 0; d < 4; d++) {

int ni = tmp.a + dir[d][0], nj = tmp.b + dir[d][1];

if (check(ni, nj) && !vi[ni][nj] && cal(arr[tmp.a][tmp.b], arr[ni][nj])) {

vi[ni][nj] = 1; q.push({ ni,nj });

v.push_back({ ni,nj }); sum += arr[ni][nj];

}

}

}

}

void ch() {

while (!f) {

f = 1; memset(vi, 0, sizeof(vi));

for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {

if (!vi[i][j]) {

q.push({ i,j }); vi[i][j] = 1;

v.push_back({ i,j }); sum += arr[i][j]; bfs();

if (v.size() > 1) {

int tra = sum / v.size(); f = 0;

for (int i = 0; i < v.size(); i++) arr[v[i].a][v[i].b] = tra;

}

v.clear(); sum = 0;

}

}

if (!f) ans++;

}

}

int main() {

std::ios::sync_with_stdio(false); cin.tie(0);

cin >> N >> L >> R; ans = 0; sum = 0; f = 0;

for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> arr[i][j];

ch();

cout << ans;

return 0;

}