[C++]백준16234번 인구 이동

문제는 다음과 같다.

오늘은 백준16234번 인구 이동 문제를 풀어보도록 하자. 삼성 기출문제이다. BFS를 이용해서 L보다 크거나 같고 R보다 작거나 같은 차이를 보이는 인접 인덱스부분을 체크하며 큐와 인덱스저장소 벡터에 넣어준다. 그리고 인접인덱스의 value를 people변수에 중복덧셈해준다. 나라의 갯수를 뜻하는 nations또한 하나씩 늘려준다.

그 후에 만일 큐가 비었다면, 그 후에 인덱스저장소가 있는 벡터의 크기만큼 돌려서 people / nations만큼 그 좌표의 값에 할당한다. 그리고 만일 인구 수에 변화가 없을 때는 flag를 통해 만일 벡터의 사이즈가 2이상인 것이 하나도 없었다면 변화가 없는 것이므로 while문을 탈출해주었다.

                                     [코드]
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int map[51][51]; //인구 맵
bool visit[51][51]; //방문처리용 맵
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };//4방향
int N, L, R, answer = 0, people = 0, nations = 0;//입력 값, answer
bool flag = false;

struct pos {
	int y;
	int x;
};
queue<pos>Q;
vector<pos>map_pos;
bool Inbound(int y, int x) {
	return y >= 1 && y <= N && x >= 1 && x <= N;
}

void InitVisit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			visit[i][j] = false;
		}
	}
}

void BFS(int y, int x) {
	people += map[y][x];
	nations++;

	visit[y][x] = true;
	Q.push({ y,x });
	map_pos.push_back({ y,x });

	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;

		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my, mx) && !visit[my][mx]) {
				if (abs(map[my][mx] - map[y][x]) >= L &&
					abs(map[my][mx] - map[y][x]) <= R) {
					visit[my][mx] = true;
					Q.push({ my,mx });
					map_pos.push_back({ my,mx });
					people += map[my][mx];
					nations++;
				}
			}
		}
	}
	for (int i = 0; i < map_pos.size(); i++) {
		if (map_pos.size() > 1) flag = true;
		map[map_pos[i].y][map_pos[i].x] = people / nations;
	}
	map_pos.clear();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> L >> R;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];//맵 value 할당
		}
	}
	
	while (1) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (visit[i][j])continue;
				people = nations = 0;
				BFS(i, j);
			}
		}
		if (!flag) break;
		InitVisit();
		flag = false;
		answer++;
	}
	cout << answer;
}