<Baekjoon> #16234 BFS_인구 이동 c++

#16234 인구이동

💬 문제정리

• 국경선을 공유하는 두 나라의 인구 차이가 L이상, R이하라면 하루동안 국경선을 연다
• 국경선이 열린 나라들을 연합이라고 하며 각 칸의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 개수) 가 된다
• 연합을 해체하고 모든 국경선을 닫는다
• 이 과정을 이동할 수 없을 때까지 반복한다

💬 아이디어

• 모든 땅을 차례대로 검사하는데, (r,c)칸을 한 번도 방문한 적 없고 (r,c)에서 상하좌우로 인접한 국경으로 이동할 수 있는지 검사한다
• 위의 조건을 충족하면 BFS 함수를 호출해, (r,c)칸에서 이동할 수 있는 모든 땅을 조사한다
• 이동할 수 있는 모든 땅의 좌표는 하나의 vector에 저장을 해준다 - 즉, 연합을 만든다
• 모든 탐색이 끝나면 각 칸의 인구수를 update 해준다
• (0,0)~(N-1, N-1)의 칸을 차례대로 검사했을 때 BFS 탐색이 끝나면 Day를 늘려준다
• 만약 모든 칸을 차례대로 검사했는데 BFS가 호출되지 않았다면 각 칸에서 이동할 수 있는 경우의 수가 0라는 뜻이므로 종료한다

👩‍💻1. Initialize

• 연합에 나라가 추가될 때, 그 나라의 (y,x)좌표, 인구수에 대한 정보를 가지고 오기위해 struct COUNTRY를 만든다
• 그 나라를 관리하는 연합을 만든다 vector<COUNTRY> uni;

struct COUNTRY {
	int y, x;
	int num;
};
vector<COUNTRY> uni;
vector<vector<int>> population;
bool visited[MAX][MAX] = { false };

👩‍💻2. Movable(int y, int x)

• (0,0)부터 (N-1,N-1)까지 모든 나라를 탐색하는데, 한 나라가 방문된 적이 없고 (아직 탐색을 해보지 않았거나, 다른 연합에 가입이 되어있지 않을 때), 인접한 나라로 움직일 수 있는지 살펴본다
• 인접한 나라로 움직일 수 있는 조건은 인구수의 차가 L이상 R이하 이어야하며, 인접한 나라 또한 한 번도 방문된 적이 없어야 한다

bool movable(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (abs(population[ny][nx] - population[y][x]) >= L &&
			abs(population[ny][nx] - population[y][x]) <= R &&
			!visited[ny][nx])
			return true;
	}
	return false;
}

👩‍💻3. BFS (int y, int x)

• 일반 BFS함수를 구현할 때와 별로 다를 건 없고, 현재 위치에서 다음 위치로 이동할 수 있을 때 queue와 uni 모두에 push를 해준다
• 탐색이 끝난 후에는 uni에 저장된 나라들 모두 인구수를 update해준다

void bfs(int y, int x) {
	uni.clear();
	queue<COUNTRY> q;

	q.push({ y,x,population[y][x] });
	uni.push_back({ y,x,population[y][x] });
	visited[y][x] = true;

	while (!q.empty()) {
		int cy = q.front().y;
		int cx = q.front().x;
		int cnum = q.front().num;
		q.pop();

		for (int dir = 0; dir < 4; dir++) {

		// 현재 위치에서 이동할 수 있는지
		// 이동할 수 있는 모든 나라 uni 에 push
		}
	}

	if (uni.empty()) return;

	int sum = 0;
	for (int i = 0; i < uni.size(); i++)
		sum += uni[i].num;
	int uniSize = uni.size();
	int avg = sum / uniSize;

	for (int i = 0; i < uni.size(); i++)
		population[uni[i].y][uni[i].x] = avg;
	return;
}

전체코드

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;
const int MAX = 51;

struct COUNTRY {
	int y, x;
	int num;
};
vector<COUNTRY> uni;
vector<vector<int>> population;
bool visited[MAX][MAX] = { false };

int N, L, R;

int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };

void bfs(int y, int x) {
	uni.clear();
	queue<COUNTRY> q;

	q.push({ y,x,population[y][x] });
	uni.push_back({ y,x,population[y][x] });
	visited[y][x] = true;

	while (!q.empty()) {
		int cy = q.front().y;
		int cx = q.front().x;
		int cnum = q.front().num;
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int ny = cy + dy[dir];
			int nx = cx + dx[dir];
		
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (abs(population[ny][nx] - population[cy][cx]) >= L &&
				abs(population[ny][nx] - population[cy][cx]) <= R && !visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push({ ny, nx, population[ny][nx] });
				uni.push_back({ ny, nx, population[ny][nx] });
			}
		}
	}

	if (uni.empty()) return;

	int sum = 0;
	for (int i = 0; i < uni.size(); i++)
		sum += uni[i].num;
	int uniSize = uni.size();
	int avg = sum / uniSize;

	for (int i = 0; i < uni.size(); i++)
		population[uni[i].y][uni[i].x] = avg;
	return;
}

bool movable(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (abs(population[ny][nx] - population[y][x]) >= L &&
			abs(population[ny][nx] - population[y][x]) <= R &&
			!visited[ny][nx])
			return true;
	}
	return false;
}

void solution() {
	int cnt = 0;
	bool check = false;
	while (1) {
		check = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j] && movable(i, j)) {
					bfs(i, j);
					check = true;
				}
			}
		}
		if (check) cnt++;
		else if (!check) break;

		memset(visited, false, sizeof(visited));
	}
	cout << cnt << endl;
}

void input() {
	cin >> N >> L >> R;
	population = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> population[i][j];
}

int main() {
	input();
	solution();
	return 0;
}