백준 16234번 인구 이동 C++

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

 

bfs를 이용하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <memory>
#include <queue>
#include <math.h>

using namespace std;

int n, l, r;
vector<vector<int>> v(50, vector<int>(50));
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

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++) {
			cin >> v[i][j];
		}
	}
	int cnt = 0;
	while (true) {
		int country = 0;
		queue<pair<int, int>> q;
		vector<vector<bool>> visited(n, vector<bool>(n, false));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				vector<pair<int, int>> tmp;
				tmp.push_back({ i,j });
				int uni = 0;
				int sum = 0;
				q.push({ i,j });
				visited[i][j] = true;
				country++;
				while (!q.empty()) {
					auto curr = q.front();
					q.pop();
					uni++;
					sum += v[curr.first][curr.second];
					for (int k = 0; k < 4; k++) {
						int nextRow = curr.first + dRow[k];
						int nextCol = curr.second + dCol[k];
						if (nextRow < 0 || nextRow >= n) continue;
						if (nextCol < 0 || nextCol >= n) continue;
						if (visited[nextRow][nextCol]) continue;
						if (abs(v[curr.first][curr.second]-v[nextRow][nextCol]) >= l && abs(v[curr.first][curr.second]-v[nextRow][nextCol]) <= r) {
							q.push({ nextRow,nextCol });
							tmp.push_back({ nextRow,nextCol });
							visited[nextRow][nextCol] = true;
						}
					}
				}
				int avr = sum / uni;
				for (auto a : tmp) {
					v[a.first][a.second] = avr;
				}
			}
		}
		if (country == n * n) break;
		cnt++;
	}
	cout << cnt;
}