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

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

16234번: 인구 이동

백준 16234번 인구 이동을 풀었다.

 

BFS에 구현을 섞은 문제인 것 같다.

 

1. N * N 좌표 상의 모든 점을 순회하면서 BFS를 돌린다.

2. 인구 이동이 일어났으면 변경된 map을 저장하고 1번으로, 인구 이동이 일어나지 않았으면 count를 출력하고 끝낸다.

 

BFS를 돌릴 때 방문했던 점은 다시 방문하지 않는다.

BFS코드에서 next좌표가 유효한 값일 때 cur좌표와의 인구 차이가 문제의 l이상, r이하이면 국경선을 여는 것으로 구현했다.

방문하지 않은 점이라 BFS를 돌렸는데 인구 이동이 일어나지 않았으면 flag를 0으로 유지한다.

만약 (N-1, N-1)좌표까지 flag가 0으로 유지된다면 모든 좌표에서 인구 이동이 일어나지 않은 것이므로 count를 출력하고 while문을 빠져나오면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

struct Point{
	int x;
	int y;
};
int n, l, r;
int map[50][50];
int map_temp[50][50];
int visited[50][50];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<Point> q;

int BFS() {
	int sum_union = 0;
	int divide = 0;
	int flag = 0;
	vector<Point> v;

	while (!q.empty()) {
		Point cur = q.front();
		sum_union += map[cur.x][cur.y];
		v.push_back(cur);
		q.pop();

		for (int i = 0; i < 4; i++) {
			Point next;
			next.x = cur.x + dx[i];
			next.y = cur.y + dy[i];
			if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < n
				&& visited[next.x][next.y] == 0) {
				int dif = abs(map[cur.x][cur.y] - map[next.x][next.y]);
				if (dif >= l && dif <= r) {
					visited[next.x][next.y] = 1;
					flag = 1;
					q.push(next);
				}
			}
		}
	}

	divide = (int)(sum_union / v.size());

	for (int i = 0; i < v.size(); i++) {
		Point temp = v[i];
		map_temp[temp.x][temp.y] = divide;
	}

	return flag;
}

int main() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			map_temp[i][j] = map[i][j];
		}
	}

	int count = 0;
	while (1) {
		int flag = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j] == 0) {
					Point cur = Point();
					cur.x = i;
					cur.y = j;
					q.push(cur);
					visited[i][j] = 1;
					flag +=BFS();
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = map_temp[i][j];
				visited[i][j] = 0;
			}
		}

		if (flag == 0) {
			cout << count;
			break;
		}
		count++;
	}



	return 0;
}