백준 16234 인구 이동

BOJ 16234

목표 : 조건에 맞게 인구이동이 몇 번 일어나는지 출력한다. 각 칸에서 상하좌우로 인접한 칸의 크기가 L이상 R이하라면 연합이 되고 인구 이동을 한다. 이때 각 나라의 인구 수는 (연합 국가들의 인구 수 총합 / 연합 국가 수)가 된다.
조건 : 1 <= N <= 50

해결방안

이 문제는 2단계로 구성할 수 있다.
1. 연합을 구성하고 인구이동이 일어난 후 인구 수를 구한다.
2. 각 연합들을 인구 이동 후 인구 수로 초기화한다.
만약 연합의 개수가 N*N개라면 모두 인구 이동을 하지 않으므로 마지막 인구 이동이 된다.

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
int N, L, R, dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1}, total, cnt, ans, num;
int people[51][51], visit[51][51], section[2501];

bool isin(int x, int y){
	return x>= 0 && y >= 0 && x < N && y < N;
}

void bfs(int x, int y){
	queue<pair<int,int>> Q;
	Q.push({x,y});
	visit[x][y] = num;
	while(!Q.empty()){
		int nx = Q.front().first, ny = Q.front().second;
		cnt++;
		total += people[nx][ny];
		Q.pop();
		for (int i = 0; i < 4; i++){
			int tx = nx + dx[i], ty = ny + dy[i];
			if (!isin(tx,ty) || visit[tx][ty] != -1){
				continue;
			}
			int dis = people[tx][ty] - people[nx][ny];
			if (dis < 0){dis *= -1;}
			if (L <= dis && dis <= R){
				visit[tx][ty] = num;
				Q.push({tx,ty});
			}
		}
	}
	section[num] = total / cnt; // num번 연합의 인구 이동 후 인구 수
}


int main(){
	scanf("%d%d%d",&N,&L,&R);
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			scanf("%d",&people[i][j]);
		}
	}
	while(1){
		memset(visit,-1,sizeof(visit));
		num = 0; 
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (visit[i][j] == -1){
					cnt = 0, total = 0;
					bfs(i,j);
					num++;
				}
			}
		}
		if (num == N*N){
			break;
		}
		ans++;
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				people[i][j] = section[visit[i][j]];
			}
		} 
	}
	printf("%d\n",ans);
	
	return 0;
}