백준 16234 c++ "인구이동" -[PlusUltraCode]

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

16234번: 인구 이동

[필자 사고]

이 문제는 BFS()탐색을 이용하여 푸는 문제이다.

 

필자는 2차원 배열의 Union을 활용하여 문제를 풀었다.

 

코드가 매우 복잡하여 문제를 해결하고 다른 분들의 코드를 확인한 결과 2차원 배열 Union을 쓰지 않고도

 

BFS하나로 해결한 모습을 알 수 있었다. BFS탐색에 관하여 많이 깨닫게 되는 문제였다.

 

[소스 코드]

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

typedef pair<int, int> Node;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int N, L, R;
vector<vector<Node>> parent;
Node find(Node a) {
	if (a == parent[a.first][a.second]) {
		return a;
	}
	return parent[a.first][a.second] = find(parent[a.first][a.second]);
}
void Union(Node a, Node b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		parent[b.first][b.second] = a;
	}
}
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}
bool IncludedLR(int num1, int num2) {
	int dif = max(num1, num2) - min(num1, num2);
	if (dif >= L && dif <= R)return true;
	return false;
}
bool IsSameUnion(Node a, Node b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	return false;
}
vector<vector<Node>> Arr;
vector<vector<bool>> visited;
bool gameOver = false;

void Input() {
	cin >> N >> L >> R;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			int num;
			cin >> num;
			Arr[i][k].first = num;
			Arr[i][k].second = -1;
		}
	}
}

void MakeUnionArr() {
	parent.clear();
	parent.resize(N);
	
	vector<vector<bool>> visited2;
	visited2.resize(N);
	for (int i = 0; i < N; i++) {
		visited2[i].resize(N, false);
		parent[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			parent[i][k] = { i,k };
		}
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			int nowSero = i;
			int nowGaro = k;
			for (int j = 0; j < 4; j++) {
				int nextSero=nowSero + dy[j];
				int nextGaro = nowGaro + dx[j];
				if (Inside(nextSero, nextGaro) &&
					IncludedLR(Arr[nowSero][nowGaro].first, Arr[nextSero][nextGaro].first)) {
					Node now = { nowSero,nowGaro };
					Node next = { nextSero, nextGaro };
					if (find(now) != find(next)) {
						Union(now, next);
					}
				}
			}
		}
	}
}

int BFS(int sero, int garo, int level) {
	int check = 0;
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			Node now = { nowSero,nowGaro };
			Node next = { nextSero,nextGaro };
			if (Inside(nextSero, nextGaro) &&
				visited[nextSero][nextGaro]==false&&
				IsSameUnion(now, next)) {
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
				Arr[nextSero][nextGaro].second = level;
				Arr[nowSero][nowGaro].second = level;
				check++;
			}
		}
	}



	return check;
}

void CheckUnionCount() {
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N, false);
	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (visited[i][k] == true)continue;
			int check =BFS(i, k, count);
			if (check != 0) count++;
			
		}

	}
	if (count == 0) {
		gameOver = true;
		return;
	}
	vector<vector<Node>> Tank;
	Tank.resize(count);
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Arr[i][k].second == -1)continue;
			Tank[Arr[i][k].second].push_back({ i,k });
		}
	}
	for (int i = 0; i < count; i++) {
		int changeN = Tank[i].size();
		int changePerson = 0;
		for (int k = 0; k < Tank[i].size(); k++) {
			int sero = Tank[i][k].first;
			int garo = Tank[i][k].second;
			changePerson += Arr[sero][garo].first;
		}
		int inputPerson = changePerson / changeN;
		for (int k = 0; k < Tank[i].size(); k++) {
			int sero = Tank[i][k].first;
			int garo = Tank[i][k].second;
			Arr[sero][garo].first = inputPerson;
		}
	}


}

void Print() {
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cout << Arr[i][k].first << " ";
		}
		cout << '\n';
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	int count = 0;
	while (1) {
		
		MakeUnionArr();
		CheckUnionCount();
	
		if (gameOver == true) {
			cout << count;
			return 0;
		}
		count++;
		for (int i = 0; i < N; i++) {
			for (int k = 0; k < N; k++) {
				Arr[i][k].second = -1;
			}
		}
	}
	cout << count;
}