[백준 16234] 인구 이동

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

16234번: 인구 이동

요구사항

인구 이동이 최대 몇번 일어나는지 구하기

 

풀이

1. bfs로 구역 나눠주기

2. bfs로 나눈 구역의 합/count를 다시 넣어주기

3. bfs가 진입 안될때까지 반복

 

disjoint로 풀어질듯한데...흠냐

#include <iostream>
#include <queue>
#include <math.h>
#include <vector>
#include <string.h>
using namespace std;
struct go {
	int r;
	int c;
};

int n, ll, rr;
int map[51][51];
int visit[51][51];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
void solve() {
	int cnt = 0;
	while (true) {
		memset(visit, 0, sizeof(visit));
		vector<int> v;
		int num = 0;
		int gameflag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int r = i;
				int c = j;
				int flag = 0;
				for (int k = 0; k < 4; k++) {
					int nr = r + dr[k];
					int nc = c + dc[k];
					if (nr < 0 || nc < 0 || nr >= n || nc >= n) {
						continue;
					}
					if (visit[nr][nc] >0)
						continue;
					if (abs(map[r][c] - map[nr][nc]) >= ll && abs(map[r][c] - map[nr][nc]) <= rr) {
						flag = 1;
					}
				}
				if (flag == 1) {
					gameflag = 1;
					int count = 1;
					num++;
					int tempsum = map[r][c];
					queue<go> q;
					q.push({ r,c });
					visit[r][c] = num;
					while (!q.empty()) {
						int nr = q.front().r;
						int nc = q.front().c;
						q.pop();
						for (int k = 0; k < 4; k++) {
							int nnr = nr + dr[k];
							int nnc = nc + dc[k];
							if (nnr < 0 || nnc < 0 || nnr >= n || nnc >= n) continue;
							if (visit[nnr][nnc] > 0) continue;
							if (abs(map[nr][nc] - map[nnr][nnc]) >= ll &&abs(map[nr][nc] - map[nnr][nnc]) <= rr) {
								visit[nnr][nnc] = num;
								count++;
								q.push({ nnr,nnc });
								tempsum += map[nnr][nnc];
							}
						}
					}
					tempsum = tempsum / count;
					v.push_back(tempsum);
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] > 0) {
					int sum = v.at(visit[i][j] - 1);
					map[i][j] = sum;
				}
			}
		}
		if (gameflag == 0)
		{
			ans = cnt;
			return;
		}
		cnt++;
	}
}
int main() {
	cin >> n >> ll >> rr;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	cout << ans << endl;
}