백준 16234번: 인구 이동

[문제 링크]

16234번: 인구 이동

---

모든 나라를 방문할 때 까지 너비 우선 탐색을 통해 인구수 차이가 L이상 R이하인 나라들을 연합국가로 묶는다.

그다음 문제에 명시된대로 (연합 인구수 / 연합 국가수) 만큼의 인구로 인구 이동을 시킨다.

 

인구 이동이 없을 때 까지 위 과정을 반복하면 원하는 결과를 얻을 수 있다.

---

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

struct Pos {
	int y;
	int x;
};

vector<vector<int>> board(50, vector<int>(50, 0));
bool visited[50][50];
int N, L, R;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int getCountryDifference(int a, int b) {
	if (a > b) return a - b;
	else return b - a;
}

vector<Pos> bfs(Pos start) {
	vector<Pos> ret;
	ret.push_back(start);

	queue<Pos> q;
	q.push(start);
	visited[start.y][start.x] = true;

	while (!q.empty()) {
		Pos here = q.front();
		int population = board[here.y][here.x];
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };

			if(there.y >= 0 && there.y < N && there.x >= 0 && there.x < N)
				if (!visited[there.y][there.x]) {
					int nextPopulation = board[there.y][there.x];
					int diff = getCountryDifference(population, nextPopulation);

					if (diff >= L && diff <= R) {
						visited[there.y][there.x] = true;
						ret.push_back(there);
						q.push(there);
					}
				}
		}
	}

	return ret;
}

bool bfsAll() {
	vector<vector<int>> temp;
	temp = board;

	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				vector<Pos> isUnion = bfs({ i,j });
				int cnt = isUnion.size();
				int sum = 0;
				for (int k = 0; k < cnt; k++)
					sum += board[isUnion[k].y][isUnion[k].x];
				for (int k = 0; k < cnt; k++)
					temp[isUnion[k].y][isUnion[k].x] = sum / cnt;
			}
		}

	if (temp == board)
		return true;
	else {
		board = temp;
		return false;
	}
}

int main(void) {
	cin >> N >> L >> R;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	int result = 0;
	while (!bfsAll()) {
		memset(visited, false, sizeof(visited));
		result++;
	}

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day