백준 16234 인구 이동

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

16234번: 인구 이동

- 그래프 탐색을 활용하는 구현 문제이다.

- 시간 복잡도는 알 수가 없다.. 언제까지 인구 이동이 일어날 지를 모르기 때문

- 가장 먼저, 모든 영역에 대해 BFS를 진행한다. 단 이미 다른 연합에 속한 영역은 진행하지 않는다. BFS를 진행할 때 마다 연합의 번호를 초깃값 1부터 1씩 늘려주면서 연합의 번호를 표시를 한다. 이는 나중에 인구 이동을 하기 위함이다.

- 그 후, 모든 영역들이 어떤 연합에 속했는지를 구하면, 인구 이동을 진행한다. 이전에 BFS를 하는 과정에서 구했던 각 연합의 수 및 각 연합의 총 인구 수를 활용하여 최신화를 해 주면 된다.

- 필자는 로직을 일찍 구현을 했는데, 디버깅하는데만 거의 1시간을 써버렸다. 그러다가 찾은 이유는 연합의 가능한 최대 경우의 수가 2500(50x50) 이었던 것.. 자꾸 segmentation fault가 떠서 미치는 줄 알았다. ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
int arr[50][50];
int visited[50][50];
int sum_of_union_person[2501];
vector<pair<int, int>> union_group[2501];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int n, l, r, union_num;

void BFS(int start_x, int start_y) {
	union_num++;
	queue<pair<int, int>> q;
	visited[start_x][start_y] = union_num;
	q.push({ start_x,start_y });
	union_group[union_num].push_back({ start_x,start_y });
	sum_of_union_person[union_num] += arr[start_x][start_y];
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny] || abs(arr[x][y] - arr[nx][ny]) < l || abs(arr[x][y] - arr[nx][ny]) > r) continue;
			visited[nx][ny] = union_num;
			q.push({ nx,ny });
			union_group[union_num].push_back({ nx,ny });
			sum_of_union_person[union_num] += arr[nx][ny];
			
		}
	}
}
int main() {
	int answer = 0;
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	while (1) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				BFS(i, j);
			}
		}
		if (union_num == n * n) break;
		// 인구 이동
		for (int i = 1; i <= union_num; i++) {
			int n = union_group[i].size();
			int value = sum_of_union_person[i] / n;
			for (int j = 0; j < union_group[i].size(); j++) {
				int x = union_group[i][j].first;
				int y = union_group[i][j].second;
				arr[x][y] = value;
			}
			while (!union_group[i].empty()) union_group[i].pop_back();
		}
		answer++;
		union_num = 0;
		memset(sum_of_union_person, 0, sizeof(sum_of_union_person));
		memset(visited, 0, sizeof(visited));
		
	}
	cout << answer;
	return 0;
}