[백준 16234] 인구 이동

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static int idSel;
static int unionCnt;

class Country {
public:
	int id;
	int people;
public:
	Country() {
		id = -1;
		people = 0;
		idSel = 0;
		unionCnt = 0;
	}

	void setId(int _id) {
		id = _id;
	}
	int getId() {
		return id;
	}

	void setPeople(int _people) {
		people = _people;
	}
	int getPeople() {
		return people;
	}

	bool isUnion(Country &cntr, const int L, const int R) {
		if(getPeople() >= cntr.getPeople()){
			if (getPeople() - cntr.getPeople() >= L && 
				getPeople() - cntr.getPeople() <= R) {
				return true;
			}
		}
		else if(getPeople() <= cntr.getPeople()){
			if (cntr.getPeople() - getPeople() >= L &&
				cntr.getPeople() - getPeople() <= R) {
				return true;
			}
		}
		return false;
	}

	void unionCountry(Country &cntr) {
		if(cntr.getId() == -1){
			//상대국이 어디에도 소속되어있지 않니?
			if (getId() == -1) {
				//자신이 어디에도 소속되어있지 않니?
				//cout << "상대국과 자신이 어디에도 소속되어있지 않니?" << endl;
				cntr.setId(idSel);
				setId(idSel);
				idSel++;
			}
			else {
				//상대국이 소속되지 않고 자신은 소속되있니?
				cntr.setId(getId());
			}
		}
		else {
			//상대국이 소속되어있니?
			if (getId() == -1) {
				//자신이 어디에도 소속되어있지 않니?
				setId(cntr.getId());
			}
			else {
				//상대국과 자신 둘 다 소속되었니?
				if (getId() < cntr.getId()) {
					cntr.setId(getId());
				}
				else {
					setId(cntr.getId());
				}
				//더 작은 id에 통합
			}
		}
	}
};

int main(void) {
	int N, L, R;
	int result = 0;
	//L이상 R이하

	cin >> N;
	cin >> L;
	cin >> R;

	//차이값
	Country **map = new Country*[N];
	for (int i = 0; i < N; i++) {
		map[i] = new Country[N];
	}
	//맵 생성 완료
	int num;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> num;
			map[i][j].setPeople(num);
		}
	}
	//인구 수 조절
	
	enum { UP, LEFT, RIGHT, DOWN };
	const int MAX_ARR = N - 1;
	//이동 횟수

	vector<pair<int, int> > idList;
	int cnt = 0;

	int **idMap = new int*[N];
	for (int i = 0; i < N; i++) {
		idMap[i] = new int[N];
	}
	//아이디 맵 생성
	int **peopleMap = new int*[N];
	for (int i = 0; i < N; i++) {
		peopleMap[i] = new int[N];
	}
	//people 맵 생성

	bool isEqual = false;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			idMap[i][j] = -1;
			peopleMap[i][j] = -1;
		}
	}
	while (true) {
		while (true) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					//cout << i << ',' << j << " 비교" << endl;
					if (i > 0) {
						if (map[i][j].isUnion(map[i - 1][j], L, R)) {
							//윗칸이 만약 연합국 대상이냐?
							map[i][j].unionCountry(map[i - 1][j]);
						}
					}
					//위에 확인

					if (j > 0) {
						if (map[i][j].isUnion(map[i][j - 1], L, R)) {
							//왼쪽이 만약 연합국 대상이냐?
							map[i][j].unionCountry(map[i][j - 1]);
						}
					}
					//왼쪽 확인

					if (j < MAX_ARR) {
						if (map[i][j].isUnion(map[i][j + 1], L, R)) {
							//오른쪽이 만약 연합국 대상이냐?
							map[i][j].unionCountry(map[i][j + 1]);
						}
					}
					//오른쪽 확인

					if (i < MAX_ARR) {
						if (map[i][j].isUnion(map[i + 1][j], L, R)) {
							//아래가 만약 연합국 대상이냐?
							map[i][j].unionCountry(map[i + 1][j]);
						}
					}
					//아래 확인
				}
			}
			isEqual = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j].getId() != idMap[i][j]) {
						isEqual = true;
						goto label;
					}
				}
			}
			//아이디 맵과 수정 후 맵이 같은지 비교
		label:
			if (!isEqual) break;
			//만약 같으면 id 값 부여 끝.

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					idMap[i][j] = map[i][j].getId();
				}
			}
			//id map 값을 대입함
		}
		
		////출력 화면
		//cout << endl;
		//for (int i = 0; i < N; i++) {
		//	for (int j = 0; j < N; j++) {
		//		cout << map[i][j].getPeople() << '(' << map[i][j].getId() << ')' << ' ';
		//	}
		//	cout << endl;
		//}
		////출력화면

		for (int i = 0; i < idSel; i++) {
			idList.push_back(pair<int, int>(0, 0));
		}
		//id갯수만큼 공간넓힘
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].getId() != -1) {
					idList[map[i][j].getId()].second += map[i][j].getPeople();
					idList[map[i][j].getId()].first++;
				}
			}
		}
		//id에 해당하는 값 누적
		if (idList.size() > 0) {
			result++;
			for (int i = 0; i < idList.size(); i++) {
				for (int j = 0; j < N; j++) {
					for (int k = 0; k < N; k++) {
						//if (map[j][k].getId() != -1 && idList[i].first != int(0) && idList[i].second != int(0)) {
							/*cout << "i is " << i << endl;
							cout << "idList[i].first : " << idList[i].first << endl;
							cout << "idList[i].second : " << idList[i].second << endl;*/
							if(map[j][k].getId() == i) map[j][k].setPeople(idList[i].second / idList[i].first);
						//}
					}
				}
			}
		}
		//인구 이동
		idList.clear();

		isEqual = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].getPeople() != peopleMap[i][j]) {
					isEqual = true;
					goto label2;
				}
			}
		}
		//피플 맵과 수정 후 맵이 같은지 비교
	label2:
		if (!isEqual) { break; }
		//만약 같으면 피플 값 부여 끝.

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				peopleMap[i][j] = map[i][j].getPeople();
			}
		}
		//피플 map 값을 대입함

		idSel = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j].setId(-1);
			}
		}
		//id 초기화
	}
	//연합국 생성
	cout << result;
	//system("pause");
	return 0;
}