[BOJ] #16234 _ 인구 이동

[인구 이동] https://www.acmicpc.net/problem/16234

16234번: 인구 이동

bfs를 이용하는 문제이다.

move_q라는 큐를 이용하여 인구 차이가 L 이상 R이하인 곳을 모두 알아내었고,

국경선이 열린 곳의 좌표를 set_q에 저장하여, 인구 이동이 끝난 후 인구수를 세팅해주었다.

 

완전히 인구 이동이 끝날 때 까지 while문으로 계속 반복하며,

checkFinish 함수를 통해 이동이 끝났는지 확인 후 while문을 종료시켜주는 방식으로 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAX 50

using namespace std;

int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 };
int N, L, R, cnt;
int map[MAX][MAX], chk[MAX][MAX];

void initChk();
int checkFinish();
void solve();
int main() {
	scanf("%d %d %d", &N, &L, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	solve();
	printf("%d\n", cnt);

	return 0;
}

void initChk() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) chk[i][j] = 0;
	}
}

int checkFinish() {
	int tmp_y, tmp_x;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 4; k++) {
				tmp_y = i + dy[k];
				tmp_x = j + dx[k];
				if (tmp_x < 0 || tmp_y < 0 || tmp_x >= N || tmp_y >= N) continue;
				if (abs(map[i][j] - map[tmp_y][tmp_x]) >= L && abs(map[i][j] - map[tmp_y][tmp_x]) <= R) return 0;
			}
		}
	}

	return 1;
}

void solve() {
	int val, tmp_y, tmp_x, y, x;
	queue<pair<int, int> >move_q, set_q;

	while (1) {
		if (checkFinish()) break;
		
		cnt++;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (chk[i][j]) continue;
				move_q.push(make_pair(i, j));
				chk[i][j] = 1;
				val = 0;

				while (!move_q.empty()) {
					y = move_q.front().first;
					x = move_q.front().second;
					move_q.pop();
					set_q.push(make_pair(y, x));
					val += map[y][x];

					for (int k = 0; k < 4; k++) {
						tmp_y = y + dy[k];
						tmp_x = x + dx[k];
						if (tmp_x < 0 || tmp_y < 0 || tmp_x >= N || tmp_y >= N) continue;
						if (chk[tmp_y][tmp_x]) continue; //
						if (abs(map[y][x] - map[tmp_y][tmp_x]) < L || abs(map[y][x] - map[tmp_y][tmp_x]) > R) continue;
						move_q.push(make_pair(tmp_y, tmp_x));
						chk[tmp_y][tmp_x] = 1;
					}
				}
				if (set_q.size() > 1) {
					val /= set_q.size();
					while (!set_q.empty()) {
						map[set_q.front().first][set_q.front().second] = val;
						set_q.pop();
					}
				}
				else set_q.pop();
			}
		}
		initChk();
	}
}