백준 16234번 : 인구 이동

• sol : 39' 55''

Learnings

• Easy

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>

#define MAX_N 50

using namespace std;

int n, l, r;
// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int grid[MAX_N][MAX_N];
int unionGrid[MAX_N][MAX_N];

struct Union {
	int population;
	int countriesNum;

	Union() : population(0), countriesNum(0) {}
	Union(int _population, int _countriesNum) :
		population(_population), countriesNum(_countriesNum) {
	}
};

vector<Union> unions;

void InitUnionGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			unionGrid[i][j] = 0;
		}
	}
}

void Init() {
	cin >> n >> l >> r;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
		}
	}

	unions.resize(n * n + 1);
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void MakeUnion(int i, int j, int id) {
	queue<pair<int, int>> q;
	q.push({ i, j });
	int population = grid[i][j], countriesNum = 1;
	unionGrid[i][j] = id;

	while (!q.empty()) {
		int ci = q.front().first, cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (InGrid(ni, nj) && unionGrid[ni][nj] == 0) {
				int gap = abs(grid[ci][cj] - grid[ni][nj]);
				if (l <= gap && gap <= r) {
					q.push({ ni, nj });
					population += grid[ni][nj];
					countriesNum++;
					unionGrid[ni][nj] = id;
				}
			}
		}
	}

	unions[id] = Union(population, countriesNum);
}

bool BorderOpen() {
	InitUnionGrid();
	int id = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (unionGrid[i][j] == 0) {
				id++;
				MakeUnion(i, j, id);
			}
		}
	}

	if (id == n * n) return false;
	else return true;
}

void Move() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			grid[i][j] = unions[unionGrid[i][j]].population / unions[unionGrid[i][j]].countriesNum;
		}
	}
}

int main() {
	Init();

	int day = 0;

	while (true) {
		// 1. border open
		if (!BorderOpen()) break;

		// 2. move
		Move();

		day++;
	}

	cout << day;
	return 0;
}