[백준] 16234 인구이동

[문제이해]

1. NxN 크기의 땅이 있다. 각각의 땅에는 나라가 하나씩 존재한다.

2. r행 c열에 있는 나라는 map[r][c] 명이 살고 있다.

3. 모든 나라는 1x1 크기이고 모든 국경선은 정사각형 형태이다.

4. 인구이동이 시작된다. 인구 이동은 아래와 같은 방법으로 진행된다. 더 이상 인구 이동이 없을때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 하루동안은 연합 이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 개수)가 된다. (소수점은 버린다.)
• 연합을 해체하고, 모든 국경선을 닫는다.

5. N,L,R이 주어졌을 때 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성해야한다.

6. 입력은 아래와 같다.

• 첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
• 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
• 인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

 

[설계]

1. DFS 또는 BFS를 통해 연합을 구한다. 연합은 BFS 방문 배열에 숫자로 기록하여 구분한다.

2. 연합을 구할때마다 그 연합을 이루고 있는 각 칸의 인구수를 구해둔다.

3. 로직은 다음과 같이 진행된다. 국경선을 BFS로 연다. 1개라도 국경선이 열린다면, 인구이동을 진행한다. 

4. 국경선이 하나라도 열리지 않다면, 인구이동을 하지않고 종료한다.

5. 인구이동 횟수를 출력한다.

 

[소스]

 

//dfs로 그룹짓고.
//지은 그룹에 대해서 맵변경하고(++인구이동횟수)
//그룹 하나라도 지을 수 없으면 종료
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;

typedef struct {
	int x, y;
}pos;

int N, L, R;
int map[50][50];
int res;
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
int cnt=1;
int visited[50][50];
int arr[2501];

bool bfs(int sx, int sy, int cnt) { 
	queue<pos> q;
	bool flag=false;

	int numOfUnited = 1;
	int sumOfUnited = map[sx][sy];

	visited[sx][sy] = cnt;
	q.push({ sx, sy });

	while (!q.empty()) {
		int x = q.front().x, y = q.front().y;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= N || nx < 0 || ny >= N || ny < 0) continue;
			if (visited[nx][ny]) continue;

			int diff = abs(map[x][y] - map[nx][ny]);
            
             //인접한 국가와 인구수 차이가 L보다 같거나 크고 R보다 작거나 같다면
             //국경선을 연다. 
			if (diff >= L && diff <= R) {
				flag = true;
				visited[nx][ny] = cnt;

				numOfUnited++;
				sumOfUnited += map[nx][ny];

				q.push({ nx,ny });
			}
		}
	}

	arr[cnt] = sumOfUnited / numOfUnited; //연합국의 인구수를 구해서 배열해 저장해둔다.

	if (!flag)
		visited[sx][sy] = 0;

	return flag;
}

bool openLoad() { //국경선을 여는 함수

	bool flag = false;
	memset(visited, 0, sizeof(visited));
	cnt = 1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == 0) {
				
				bool signal = bfs(i, j, cnt);

				if (!flag) {
					if (signal)
						flag = true;
				}

				cnt++;
			}
		}
	}

	return flag;
}

void moving() { //인구 이동을 하는 함수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) {
				map[i][j] = arr[visited[i][j]];
			}
		}
	}
}

void solve() {
	while (1) {
		if (openLoad()) {
			moving();
			res++;
		}
		else { //더 이상 인구이동이 불가능하면(국경선이 열리지 않는다면) 결과를 출력하고 종료.
			cout << res;
			return;
		}
	}
}

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();

	return 0;
}