[c++] 백준 16234, 인구 이동

백준 16234

🌲 문제 요약

주어진 특정 조건을 만족하는 경우, 이웃한 나라의 국경선을 하루간 열어 인구 이동을 진행한다고 할 때, 인구 이동이 총 며칠 동안 발생하는지 구하는 문제.

🌲 문제 풀이

인구 이동이 더 이상 발생하지 않을 때까지, 배열 a를 반복하여 탐색한다. 반복 과정에서 이웃한 두 나라가 특정 조건을 만족하는 경우엔 그러한 나라들의 좌표를 벡터 v에 추가하고, 해당 나라들의 인구 수를 새로운 값으로 초기화한다. 한 번의 인구 이동이 끝날 때마다 cnt의 값을 1만큼 증가시킨다.

🌲 주의

인구 이동이 발생한 이웃 나라가 하나라도 존재하는 경우에 flag의 값은 1이 되어 반복을 이어가며, 인구 이동이 발생한 이웃 나라가 아예 존재하지 않는 경우에만 flag의 값은 0이 되어 반복을 종료한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, l, r, a[55][55], visited[55][55], sum, cnt;
vector<pair<int, int>> v;

void dfs(int y, int x) {
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
		if (abs(a[ny][nx] - a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r) {
			sum += a[ny][nx];
			v.push_back({ny, nx});
			dfs(ny, nx);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	while (1) {
		memset(visited, 0, sizeof(visited));
		bool flag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					sum = a[i][j];
					v.clear();
					v.push_back({i, j});
					dfs(i, j);
					if (v.size() == 1) continue;
					for (pair<int, int> b : v) {
						a[b.first][b.second] = sum / v.size();
						flag = 1;
					}
				}
			}
		}
		if (!flag) break;
		cnt++;
	}
	cout << cnt << '\n';
	
	return 0;
}