BOJ 16234 : 인구이동

[정답 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;

typedef struct {
	int idx;
	int y;
	int x;

}info;

typedef struct {
	int sum;
	int num;
}comb_info;

const int MAX = 51;
int map[MAX][MAX]; //나라인구 정보
bool vis[MAX][MAX]; //탐색 체크
int N, L, R;
bool can_move = true;
//상,하,좌,우
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

vector<info> comb;
int answer = 0;

//디버깅용 프린트
void print_comb() {
	int s = comb.size();
	cout << "===========" << "\n";
	for (int i = 0; i < s; i++) {
		cout << "y:" << comb[i].y << "x:" << comb[i].x << "idx:" << comb[i].idx << "\n";
	}
}

void print_map() {
	//2차원 배열 출력법 암기..
	int col = sizeof(map[0]) / sizeof(int);
	int row = sizeof(map) / sizeof(map[0]);

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cout << map[i][j];
		}
		cout << "\n";
	}
}

int remap() {

	int s = comb.size();
	vector<comb_info> comb_check(s);

	for (int i = 0; i < s; i++) {
		int c_idx = comb[i].idx;
		int cy = comb[i].y;
		int cx = comb[i].x;

		comb_check[c_idx].sum += map[cy][cx];
		comb_check[c_idx].num += 1;
	}

	int flag = 0;
	for (int i = 0; i < comb_check.size(); i++) {
		if (comb_check[i].num >= 2) {
			flag += 1;
		}
	}

	for (int i = 0; i < s; i++) {
		int c_idx = comb[i].idx;
		int cy = comb[i].y;
		int cx = comb[i].x;

		int temp = comb_check[c_idx].sum / comb_check[c_idx].num;
		map[cy][cx] = temp;
	}
	return flag;
}

void bfs(int cy, int cx, int idx) {
	queue<pair<int, int>> q;
	q.push({ cy,cx });
	comb.push_back({ idx,cy,cx });
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		int cur_y = cur.first;
		int cur_x = cur.second;
		vis[cur_y][cur_x] = true;
		for (int dir = 0; dir < 4; dir++) {
			int ny = cur_y + dy[dir];
			int nx = cur_x + dx[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (vis[ny][nx] == true) continue;
			//int diff = abs(map[ny][nx] - map[cur_y][cur_x]);
			int diff = map[ny][nx] - map[cur_y][cur_x];
			if (diff < 0) diff = -diff;
			if (L <= diff && diff <= R) {
				q.push({ ny,nx });
				comb.push_back({ idx, ny,nx });
				vis[ny][nx] = true;
			}
		}
	}
}

void solve() {
	int tmpcheck;
	while (can_move) {
		memset(vis, false, sizeof(vis));
		comb.clear();
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (vis[i][j] == false) {
					bfs(i, j, cnt);
					cnt++;
				}
			}
		}
		int tmpcheck = remap();
		//print_comb();
		//print_map();
		//cout << tmpcheck << "\n";
		if (tmpcheck != 0) {
			answer += 1;
		}
		//answer += 1;
		if (tmpcheck == 0) can_move = false;
	}
}

int main() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	cout << answer << "\n";

	return 0;
}