[BOJ] 16234 : 인구 이동 - travelbeeee

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

---

[알고리즘풀이]

Union - Find 를 이용해서 문제를 해결했습니다.

( 대부분 DFS, BFS로 문제를 푸셨더라고요....!! DFS, BFS 풀이는 다른 분들 블로그 참고하시면 될 것 같습니다. )

 

n : 도시의 크기를 나타내는 수 ( n * n : 도시의 크기 )

N[x][y] : 현재 도시별 인구가 담겨있는 배열.

 

1) 번호 부여.

(i , j) 도시의 번호 = i * n + j 로 정의하면, 모든 도시에게 0 ~ (n * n - 1)까지 번호를 하나씩 부여할 수 있습니다.

 

2) Union - find

(0, 0)부터 (n-1, n-1)까지 모든 도시에게 번호를 부여한 후, 1차원 배열로 Union - find 를 진행합니다.

N[i][j] 와 N[k][l] 이 인접해있고, 두 도시의 인구 차이가 L 보다 크거나 같고, R 보다 작거나 같으면 (i , j) 와 (k, l)을 Union(Merge) 해줍니다.

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n - 1; j++)
				if (check(abs(N[i][j] - N[i][j + 1]))) {
					merge(i * n + j, i * n + (j + 1));
					stop++;
				}

		for (int j = 0; j < n; j++)
			for (int i = 0; i < n - 1; i++)
				if (check(abs(N[i][j] - N[i + 1][j]))) {
					merge(i * n + j, (i + 1) * n + j);
					stop++;
				}

3) 도시 인구 초기화.

조건에 해당되서 Union된 도시가 있다면, 인구 이동을 진행해야 합니다.

각 도시별로 root 값을 다 find 한 후, 같은 root 값을 가지는 도시들은 하나의 vector에 Push합니다.

		vector<int> g[2500];
		for (int i = 0; i < n * n; i++){
			g[find(i)].push_back(i);
		}

이제 root 값이 같은 도시들은 모두 하나의 vector에 들어가 있습니다.

따라서,  size가 0 보다 큰 모든 vector 들(root 값이 같은 도시가 있는 도시들)을 하나씩 순회하며 인구를 초기화해주면 됩니다.

		for (int i = 0; i < n * n; i++) {
			int cnt = g[i].size();
			if (cnt > 0) {
				int sum = 0;
				for (int j = 0; j < g[i].size(); j++) {
					sum += N[g[i][j] / n][g[i][j] % n];
				}
				int avg = sum / cnt;
				for (int j = 0; j < g[i].size(); j++) {
					N[g[i][j] / n][g[i][j] % n] = avg;
				}
			}
		}

 

4) 최종 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int n, l, r, N[50][50];
int p[2500] = {};
int h[2500] = {};
int f[2500] = {};

bool check(int a) {
	if (l <= a && a <= r)
		return true;
	return false;
}

int find(int x) {
	if (p[x] == x)
		return x;
	else {
		return p[x] = find(p[x]);
	}
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y)
		return;

	if (h[x] < h[y])
		p[x] = y;
	else {
		p[y] = x;
		if (h[x] == h[y])
			h[x]++;
	}
	return;
}

int main(void) {
	cin >> n >> l >> r;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> N[i][j];

	int c = 0;

	while (1) {
		for (int i = 0; i < n * n; i++) {
			p[i] = i;
			h[i] = 0;
		}

		int stop = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n - 1; j++)
				if (check(abs(N[i][j] - N[i][j + 1]))) {
					merge(i * n + j, i * n + (j + 1));
					stop++;
				}

		for (int j = 0; j < n; j++)
			for (int i = 0; i < n - 1; i++)
				if (check(abs(N[i][j] - N[i + 1][j]))) {
					merge(i * n + j, (i + 1) * n + j);
					stop++;
				}
		if (stop == 0)
			break;

		vector<int> g[2500];
		for (int i = 0; i < n * n; i++){
			g[find(i)].push_back(i);
		}

		for (int i = 0; i < n * n; i++) {
			int cnt = g[i].size();
			if (cnt > 0) {
				int sum = 0;
				for (int j = 0; j < g[i].size(); j++) {
					sum += N[g[i][j] / n][g[i][j] % n];
				}
				int avg = sum / cnt;
				for (int j = 0; j < g[i].size(); j++) {
					N[g[i][j] / n][g[i][j] % n] = avg;
				}
			}
		}
		c++;
	}
	cout << c;
}

---