[BOJ/C++]16234(인구 이동)

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

비슷한 문제: 1926(그림)
Link: https://www.acmicpc.net/problem/1926

• 해당 문제에서는 이어진 칸의 집합을 하나의 단위로 본다. 이를 조금 응용하여 이 문제도 풀 수 있었다.

1. 인구 이동을 위해 국경선을 오픈한다 -> 칸끼리 연결되는 경우가 발생한다는 의미이므로 BFS 예상
2. 입력 조건으로 배열의 크기가 최대 50x50까지 주어진다 -> BFS 기반의 Simulation으로 예상

위의 두 아이디어와 문제의 조건들로부터 이중 for문을 통해 각 노드를 필요한 만큼 탐색하되, 해당 탐색을 몇 번 반복했는지가 관건이므로 while문으로 이를 감싸서 문제를 해결하고자 함

다만, 그다지 깔끔한 문제 풀이 방법이 아니라서 추후에 시간을 내서 코드 개선을 하고자 한다.

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

#define MAX 50
#define p pair<int, int>
int n, l, r;
int a[MAX][MAX];
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };

void input() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}
}

int solution() {
	int day = 0;
	while (1) {
		int count = 0;
		bool vis[MAX][MAX]{ 0 };
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (vis[i][j]) continue;
				int sum = 0;
				vector<p> countryList;
				queue<p> q;
				q.push(make_pair(i, j));
				countryList.push_back(make_pair(i, j));
				vis[i][j] = 1;
				while (!q.empty()) {
					p cur = q.front(); q.pop();
					sum += a[cur.first][cur.second];
					for (int dir = 0; dir < 4; ++dir) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
						if (vis[nx][ny]) continue;
						int dif = abs(a[nx][ny] - a[cur.first][cur.second]);
						if (dif < l || dif > r) continue;
						vis[nx][ny] = 1;
						q.push(make_pair(nx, ny));
						countryList.push_back(make_pair(nx,ny));
					}
				}
				int Size = countryList.size();
				if (Size > 1) ++count;
				for (int k = 0; k < Size; ++k) {
					a[countryList[k].first][countryList[k].second] = sum / Size;
				}
			}
		}
		if (count == 0) break;
		++day;
	}
	return day;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	input();
	cout << solution();
	return 0;
}