인구 이동

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

16234번: 인구 이동

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct pos {
	int y, x;
};

int n, l, r;
int map[51][51];
int answer = 0;

int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };

void create_area(int sy, int sx, int visited[][51], int status[][51], int index, int& count, int& sum) {

	queue<pos> q;
	pos head;
	head.y = sy;
	head.x = sx;
	visited[sy][sx] = 1;
	q.push(head);

	while (!q.empty()) {
		pos cur = q.front(); q.pop();
		status[cur.y][cur.x] = index;
		count++;
		sum += map[cur.y][cur.x];

		for (int dir = 0; dir < 4; dir++) {
			pos next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];

			if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) continue;
			int delta = abs(map[cur.y][cur.x] - map[next.y][next.x]);
			if (visited[next.y][next.x] == 0 && l <= delta && delta <= r) {
				visited[next.y][next.x] = 1; q.push(next);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> l >> r;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
	bool is_update = true;
	while (is_update) {
		is_update = false;
		int status[51][51] = { 0, };
		int count[2501] = { 0, };
		int sum[2501] = { 0, };
		int area_index = 0;
		int visited[51][51] = { 0, };
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (status[y][x] == 0) {
					area_index++;
					create_area(y, x, visited, status, area_index, count[area_index], sum[area_index]);
				}
			}
		}
		for (int y = 0; y < n; y++) { //수정되었으면 ++
			for (int x = 0; x < n; x++) {
				int index = status[y][x];
				int avg = sum[index] / count[index];
				if (map[y][x] != avg) {
					map[y][x] = avg;
					is_update = true;
				}
			}
		}
		if (is_update) answer++;
	}
	cout << answer << "\n";
	return 0;
}