백준 16234 인구 이동

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

16234번: 인구 이동

유형: bfs, 시뮬레이션

• 나라별로 구분 map을 구분 짓는다. bfs로 알 수 있음
• bfs가 끝 났을 때 avg함수를 사용하여 map을 평균 값으로 업데이트 한다.

/*
	국경선을 번호로 구분한다
	type_sum[index]으로 구분
	type_num[index] 평균 구할 때 사용
	index가 의미하는건 국경선이다
	type에는 각 나라가 더한 값을 집어 넣는다.
	
	main
		입력
		완전탐색
			-1인경우만
				sol
		if flag
			avg
			flag=false
			유니온 -1로 초기화
	sol
		bfs사용
		while
			cur
			next
			if next union-1만,범위,차이값
				push
				union <- 유형별로 업데이트
				flag=true
	avg
		완탐
			유니온이 != -1
				type_sum[union[i][j]] += map[i][j]
				type_num[union[i][j]] ++;
		완탐
			map[i][j]=type_sum[유니온]/type_num[유니온]
*/
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int N, L, R;
int map[50][50];
int uni[50][50];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int flag = false;
int ans=0;

void sol(int y,int x,int ty)
{
	queue<pair<int, int>> q;
	q.push({ y,x });
	uni[y][x] = ty;
	while (!q.empty())
	{
		int cx = q.front().second;
		int cy = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && uni[ny][nx] == -1
				&& abs(map[ny][nx] - map[cy][cx]) >= L &&
				abs(map[ny][nx] - map[cy][cx]) <= R)
			{
				q.push({ ny,nx });
				uni[ny][nx] = ty;
				flag = true;
			}
		}
	}
}
void avg()
{
	vector<int> type_sum(2500);
	vector<int> type_num(2500);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (uni[i][j] != -1)
			{
				type_sum[uni[i][j]] += map[i][j];
				type_num[uni[i][j]]++;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			map[i][j] = type_sum[uni[i][j]] / type_num[uni[i][j]];
		}
	}
}
int main() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
		}
	}
	memset(uni, -1, sizeof(uni));
	while (1)
	{
		int ty = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (uni[i][j] == -1)
				{
					sol(i, j, ty);
					ty++;
				}
			}
		}
		if (flag)
		{
			avg();
			flag = false;
			memset(uni, -1, sizeof(uni));
			ans++;
		}
		else
			break;
	}
	cout << ans;
}