[PS][기출문제][삼성]/[BOJ][16234][인구이동]

boj16234.cpp

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n,l,p;
int map[50][50];
int region[50][50];
int comp[2501]; // comp[i] : i번째 dfs의 연결요소 갯수
int people[2501]; //people[i] : i번째 dfs의 총 사람 수
bool visited[50][50];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

void showR(void) {
	int i = 0, j = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cout << region[i][j] << ' ';
		}
		cout << "\n";
	}
}

void show(void) {
	int i = 0, j = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << "\n";
	}
}

bool in_range(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
}

void dfs(int x, int y, int d) {
	int nx = 0, ny = 0, k=0;
	region[x][y] = d;
	comp[d]++;
	people[d] += map[x][y];
	visited[x][y] = true;
	for (k = 0; k < 4; k++) {
		nx = x + dx[k];
		ny = y + dy[k];
		if (!in_range(nx, ny)) continue;
		if (visited[nx][ny]) continue;
		int gap = abs(map[x][y] - map[nx][ny]);
		if (l <= gap && gap <= p) {
			dfs(nx, ny,d);
		}
	}
}

void setCivil(void){
	int i = 0, j = 0, d=0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			d = region[i][j];
			if (comp[d] == 1) continue;
			map[i][j] = people[d] / comp[d];
		}
	}
}

bool peopleMoved(int d) {
	int i = 0;
	for (i = 1; i < d; i++) {
		if (comp[i] > 1) return true;
	}
	return false;
}

int solve(void) {
	int i = 0, j = 0, district = 1;;
	//connected component 갯수 구하고
	int ret = 0;
	while (true) {
		district = 1;
		memset(visited, false, sizeof(visited));
		memset(comp, 0, sizeof(comp));
		memset(people, 0, sizeof(people));
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				dfs(i, j, district++);
			}
		}
		if (peopleMoved(district)) {
			ret++;
			setCivil();
		}
		else {
			break;
		}
	}
	return ret;
}

int main(void) {
	int i=0,j=0;
	cin >> n >> l >> p;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	cout << solve();
	return 0;
}