[BOJ][16234] 인구이동

문제

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

풀이

연합국을 찾고, 연합국의 위치에 평균을 넣어주는 것을 반복하면서 더이상 연합국이 없을 때까지 이 과정을 반복하는 문제입니다.

1. 모든 위치를 탐색하여 국경선을 공유할 나라를 모읍니다. 

1-1. 한칸 한칸 탐색하는데, 두 나라의 인구 차이가 L과 R사이에 존재할 경우 team 벡터에 담고 인구 수를 카운팅해줍니다.

1-2. 연합국을 다 모았으면 인구 수/team.size()를 이용해 평균을 구합니다.

1-3. 다음 연합국을 모으기 위해 team벡터와 인구총합을 초기화 해줍니다.

2. isFin 이라는 변수를 두고, 연합국이 있을 경우 while문을 진행하도록 하고 없을 경우 while문을 빠져나오도록 합니다.

3. 이때, isFin이 true이면 결과값+1을 해주어 답을 구합니다.

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;
int n, l, r, res = 0;
bool isFin;
int map[51][51];
int visited[51][51];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };	
int peo_num = 0;
vector<pair<int, int>> team;
void BFS(int a, int b) {
	queue<pair<int, int>> q;
	q.push(make_pair(a, b));
	visited[a][b] = 1;
	bool isOK = false;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		team.push_back(make_pair(x, y));
		peo_num += map[x][y];
		//연합국이 있는지 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[nx][ny]==0 && (abs(map[x][y] - map[nx][ny]) >= l && abs(map[x][y] - map[nx][ny]) <= r)) {
				q.push(make_pair(nx, ny));
				visited[nx][ny] = 1;
				isOK = true;
				isFin = true;
			}
		}
	}
	//연합이 존재하지 않을 경우
	if (!isOK) {
		peo_num -= map[a][b];
		team.pop_back();
		return;
	}
	//연합 존재할 경우
	int avg = floor(peo_num / team.size());
	for (int i = 0; i < team.size(); i++) {
		map[team[i].first][team[i].second] = avg;
	}
	team.clear();
	peo_num = 0;
}
int main() {
	//입력
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	
	//종료조건
	isFin = true;
	while (isFin) {
		isFin = false;
		memset(visited, 0, sizeof(visited));
		team.clear();
		peo_num = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j] == 0) {
					BFS(i, j);
				}
			}
		}
		//인구이동이 있었을 경우
		if (isFin) {
			res++;
		}
		
	}
	cout << res;
}