백준 16234 - 인구 이동

문제링크

• 백준 16234

문제설명

• NxN 크기의 땅이 있고, 칸 하나는 나라를 의미하며 원소로는 해당 나라의 인구수가 담긴다.
• 인접한 나라들과는 국경선을 두고 있고 특정 조건에서만 국경선이 열린다. 열린 국경선을 통해 인구이동이 일어나고 로직은 다음과 같다.
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 국경선을 연다.
  • 열 수 있는 국경선이 모두 열렸다면 인구 이동을 시작한다.
  • 국경선이 열려 있는 나라끼리만 이동할 수 있고, 이를 연합이라고 부른다. 연합을 이루고 있는 각 칸의 인구수를 (연합의 총 인구수) / (연합을 이루는 칸의 개수) 에서 소수점은 버린 값으로 갱신한다.
  • 연합을 해체하고 모든 국경을 닫는다.
• 인구이동이 일어나지 않을 때까지 위 로직을 몇번 반복하는지 구한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <cmath>

using namespace std;

int N, L, R;
vector<vector<int>> land(50, vector<int>(50, 0));
int unitedNation[50][50] = { 0, }; // 연합 구역을 나타냄. 같은 연합은 같은 숫자
bool visited[50][50] = { false, };
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int Bfs(pair<int, int> spos, int area) {
	queue<pair<int, int>> q;
	int sum = 0, cnt = 0;
	q.push(spos);
	visited[spos.first][spos.second] = true;
	unitedNation[spos.first][spos.second] = area;
	sum = land[spos.first][spos.second];
	cnt = 1;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		int diff;
		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			diff = abs(land[cpos.first][cpos.second] - land[nextX][nextY]);
			if (diff<L || diff>R) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			unitedNation[nextX][nextY] = area;
			q.push(make_pair(nextX, nextY));
			sum += land[nextX][nextY];
			cnt++;
		}
	}

	return sum / cnt;
}

void MovePeople() {
	vector<int> nPeople;
	int area = 1;

	// Set Union
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (unitedNation[r][c] == 0) {
				nPeople.push_back(Bfs(make_pair(r, c), area++));
			}
		}
	}

	// update land
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int unitedNum = unitedNation[r][c];
			land[r][c] = nPeople[unitedNum - 1];
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &N, &L, &R);
	
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &land[r][c]);
		}
	}

	int ans = 0;
	vector<vector<int>> cland = land;
	while (true) {
		memset(unitedNation, 0, sizeof(unitedNation));
		memset(visited, false, sizeof(visited));
		MovePeople();
		if (cland == land) break;
		ans++;
		cland = land;
	}

	printf("%d\n", ans);
	return 0;
}