Boj 16234) 인구 이동

문제

백준 16234

설명

중복체크용 visitTB[] 말고 lockTB[] 를 또 두어서, 탐색 시에 true 로 두고 평균값으로 업데이트 할때만 false 로 초기화를 해줌.

그러면 80퍼에서 안막힘.

시간 복잡도

O(\(N^2 \times 2000\))

코드

int n, l, r;
int board[51 * 51];

inline bool Valid(int a, int b) {
	int c = abs(board[a] - board[b]);
	return l <= c && c <= r;
}

bool visitTB[51 * 51]; bool bMove = false;
int sumTB[51 * 51]; bool lockedTB[51 * 51];

void BFS(int start)
{
	int sum = 0, n_sum = 0;
	queue<int> works;
	works.push(start);
	while (!works.empty())
	{
		int cur = works.front(); works.pop();
		if (visitTB[cur]) continue;
		visitTB[cur] = true;
		lockedTB[cur] = true;

		int x = cur % n;
		int y = cur / n;
		int c = board[cur];
		sum += c;
		sumTB[n_sum++] = cur;
	
		if (x > 0 && Valid(cur, cur - 1)) works.push(cur - 1);
		if (x + 1 < n && Valid(cur, cur + 1)) works.push(cur + 1);
		if (y > 0 && Valid(cur, cur - n)) works.push(cur - n);
		if (y + 1 < n && Valid(cur, cur + n)) works.push(cur + n);
	}
	
	if (n_sum > 1)
	{
		sum /= n_sum;
		for (int i = 0; i < n_sum; i++)
		{
			board[sumTB[i]] = sum;
			lockedTB[sumTB[i]] = false;
		}
		bMove = true;
	}
}

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

	for (int i = 0; i < n * n; i++)
		cin >> board[i];
	
	int ans = 0;
	while (1)
	{
		for (int i = 0; i < n * n; i++)
			if (!visitTB[i] && !lockedTB[i]) BFS(i);
		if (!bMove) break;
		fill(visitTB, visitTB + n * n, 0);
		bMove = false;
		ans++;
	}
	cout << ans;
}