[백준] 16234번 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

DFS로 풀었다. BFS나 DFS나 아무거나로 풀어도 된다.

DFS는 연합을 만드는 과정이다. 상하좌우 탐색하면서 l개 이상 r개 이하로 차이가 나면 스택에 넣어주었다.

탐색을 하면서 그 연합에 속하는 나라의 행과 열을 pair로 묶어서 countries라는 벡터에 넣어줬다.

또한 그 연합에 속하는 나라의 인구 수를 sum에 누적해서 더해줬다.

그렇게 연합을 만든 후에 sum을 countries.size()로 나눠서 인구 수를 갱신해주었다.

countries.size()가 1이면 인구 이동이 일어나지 않는 것이고 1보다 크면 인구 이동이 일어났다는 것이므로 flag = true로 해준다.

flag가 false라는 것은 더 이상 인구 이동이 일어나지 않는다는 것이므로 while문을 빠져나온다.

가장 바깥쪽 while문은 인구이동이 몇 번 일어났는지를 세어준다.

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, l, r;
	cin >> n >> l >> r;
	vector<vector<int>> v(n, vector<int>(n));
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int moveCount = 0;
	while (true) {
		visited = vector<vector<bool>>(n, vector<bool>(n, false));
		bool flag = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					stack<pair<int, int>> stack;
					stack.push(make_pair(i, j));
					int sum = 0;
					vector<pair<int, int>> countries;
					while (!stack.empty()) {
						pair<int, int> cur = stack.top();
						stack.pop();
						int row = cur.first;
						int col = cur.second;
						if (!visited[row][col]) {
							visited[row][col] = true;
							sum += v[row][col];
							countries.push_back(cur);
							if (row + 1 < n && abs(v[row][col] - v[row + 1][col]) >= l && abs(v[row][col] - v[row + 1][col]) <= r) {
								stack.push(make_pair(row + 1, col));
							}
							if (row - 1 >= 0 && abs(v[row][col] - v[row - 1][col]) >= l && abs(v[row][col] - v[row - 1][col]) <= r) {
								stack.push(make_pair(row - 1, col));
							}
							if (col + 1 < n && abs(v[row][col] - v[row][col + 1]) >= l && abs(v[row][col] - v[row][col + 1]) <= r) {
								stack.push(make_pair(row, col + 1));
							}
							if (col - 1 >= 0 && abs(v[row][col] - v[row][col - 1]) >= l && abs(v[row][col] - v[row][col - 1]) <= r) {
								stack.push(make_pair(row, col - 1));
							}
						}
					}
					if (countries.size() > 1) {
						flag = true;
						for (int k = 0; k < countries.size(); k++) {
							int row = countries[k].first;
							int col = countries[k].second;
							v[row][col] = sum / countries.size();
						}
					}
				}
			}
		}
		if (!flag)
			break;
		moveCount++;
	}
	cout << moveCount;
	return 0;
}