[백준] 16234 인구 이동

[백준] 16234 인구 이동

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;

int N, L, R;
int board[51][51] = { 0 };

int visited[51][51] = { 0 };

int dirR[4] = { 0, 0, -1, 1 };
int dirC[4] = { 1, -1, 0, 0 };

bool inRange(int r, int c) {
	if ((r < 0) || (r >= N)) return false;
	if ((c < 0) || (c >= N)) return false;
	return true;
}

//(startR, startC)좌표 국가가 연합을 만들 수 있는지 반환
//만들 수 있는 경우 연합 만든 후 인구 이동
bool makeUnion(int startR, int startC) {
	queue<pair<int, int>> q;
	q.push({ startR, startC });

	//만들어진 연합
	vector<pair<int, int>> uni;

	while (!q.empty()) {
		int curR = q.front().first;
		int curC = q.front().second;
		q.pop();

		if (visited[curR][curC]) continue;
		visited[curR][curC] = 1;

		uni.push_back({ curR,curC });

		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d];
			int nextC = curC + dirC[d];
			if (!inRange(nextR, nextC)) continue;
			if (visited[nextR][nextC]) continue;

			int diff = abs(board[curR][curC] - board[nextR][nextC]);
			if ((L <= diff) && (diff <= R)) {
				q.push({ nextR, nextC });
			}
		}
	}

	//연합 만들어졌는지 확인
	//자기자신만 연결되어있는 경우 연합 X
	if (uni.size() == 1) return false;

	//연합 만들어진 경우 인구 이동
	int sum = 0;
	for (int i = 0; i < uni.size(); ++i) {
		sum += board[uni[i].first][uni[i].second];
	}
	int pp = sum / uni.size();
	for (int i = 0; i < uni.size(); ++i) {
		board[uni[i].first][uni[i].second] = pp;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> L >> R;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int input;
			cin >> input;
			board[i][j] = input;
		}
	}

	int answer = 0;
	while (true) {
		//방문 표시 초기화
		for (int i = 0; i < 51; ++i) {
			for (int j = 0; j < 51; ++j) {
				visited[i][j] = 0;
			}
		}

		//연합 만들기
		bool unionMade = false;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (visited[i][j]) continue;

				if (makeUnion(i, j)) {
					unionMade = true;
				}
			}
		}

		if (unionMade) answer++;
		else break;
	}

	cout << answer;
	return 0;
}