[BOJ16234] 인구이동

[BOJ16234] 인구이동

---

문제링크

---

문제 설명

• 처음 필드 한칸 마다 국경선이 존재하고, 나라가 하나씩 존재한다.
• 필드 한칸에는 그 나라에 살고 있는 인구수가 적혀있다.
• 인구 이동이 시작되면 아래 그림과 같이 진행된다. (출처: 백준 온라인저지)
• 더 이상 인구이동을 할 수 없을 때, 인구 이동이 몇번 발생하는지 구하면 된다.

---

코드 리뷰

• 어렵지 않은 문제였다. 1시간 10분 정도 걸린듯. 기출 문제중에 가장 빨리 풀었다.
• 다른 분들 코드보니깐 시간이 엄청 짧던데, 그런 부분은 더욱 발전해야 할 듯. 한번 더 풀면 시간 줄여서 코드 올리겠음.
• BFS를 통해서, 인구 이동이 가능한 칸들을 체크 배열을 통해 같은 숫자로 묶어준다.
• 묶인 칸들에 대해 그 칸들이 몇 개 존재하는지, 그리고 묶인 칸들의 인구의 합을 구한 후, 평균 값을 묶인 칸들에 재할당 한다.
• 이 과정을 반복한 후, 체크 배열에 묶이지 않는 경우, 무한 루프를 탈출하고, 카운트한 값을 출력한다.

/*BOJ16234 인구이동*/

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

int N, L, R;
int board[55][55];
int check[55][55];
int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };

typedef struct {
	int x;
	int y;
	int part_coloring;
}country;

typedef struct {
	int cnt;
	int sum;
	int result;
}map;

void bfs(int n, int m, int part) {
	queue <country> q;
	q.push({ n,m,part });
	while (q.empty() == 0) {
		int nx = q.front().x;
		int ny = q.front().y;
		int level = q.front().part_coloring;
		check[nx][ny] = level;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nnext = nx + dc[k];
			int mnext = ny + dr[k];
			if (nnext < 0 || nnext >= N || mnext < 0 || mnext >= N || check[nnext][mnext] == check[nx][ny])
				continue;
			if (abs(board[nnext][mnext] - board[nx][ny]) >= L && abs(board[nnext][mnext] - board[nx][ny]) <= R) {
				check[nnext][mnext] = level;
				q.push({ nnext,mnext,level });
			}
		}
	}
}
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", &board[i][j]);
		}
	}
	int cnt = 0;
	while (1) {
		int part_cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (check[i][j] != 0) continue;
				part_cnt++;
				bfs(i, j, part_cnt);
			}
		}
		if (part_cnt == N * N) break;

		vector <map> v(part_cnt + 1);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				v[check[i][j]].cnt++;
				v[check[i][j]].sum += board[i][j];
			}
		}
		for (int i = 1; i < part_cnt + 1; i++) {
			v[i].result = v[i].sum / v[i].cnt;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = v[check[i][j]].result;
			}
		}
		cnt++;
		memset(check, 0, sizeof(check));
	}
	printf("%d", cnt);
	return 0;
}