BOJ 14258 - XOR 그룹

* XOR 그룹

[ 분류 - DSU ]

  CS Academy Round #9의 Array Removal이라는 문제를 먼저 푸는 것을 권장합니다.

  1. 수가 작은 것 부터 제거해나가므로, 지우는 순서는 정해져 있다.

  2. k번째 수를 제거했을 때의 XOR 그룹의 합 최대값과 k+1번째 수를 제거했을 때의 XOR 그룹의 합 최대값은 서로 종속적이다.

  3. 지우는 과정에서 나오는 XOR 그룹의 합 최대가 되는 값을 출력한다.

  삭제하는 순서대로 답을 도출해내기란 쉽지 않다. 따라서 문제 접근 방식을 조금 다르게 해야하는데, 삭제하는 과정 자체에 의미가 없다는 것을 깨닫는 것부터 시작한다. 무슨 소리나면, 1.처럼 순서는 정해져 있으며, 2.처럼 서로 종속적이기 때문에 종속의 의미 지니게끔 접근하는 것이다. 주어진 순서를 그대로 거꾸로 뒤집으면 종속 속성은 지니게끔 할 수 있다.

  따라서 초기상태는 모두 지워진 상황에서 "큰 수"부터 추가하는 것이다. 큰 수를 추가해나감으로써 상하좌우 4방향에 대해 Union를 해주면 되시겠다. 그 중 현재 가장 큰 값과 합쳐서 나오는 값만을 확인해서 답을 도출해내면 된다. 어차피 가장 큰 값 하나만 원하므로 XOR union 할 때, 그 대상이 변경되는 것은 무시해도 상관 없기 때문이다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct _q { int D, v; };
bool operator<(const _q& a, const _q& b) {
	return a.D < b.D;
}
int p[1000001];
long long ans, t, s[1000001];
int find(int u) { return u == p[u] ? u : (p[u] = find(p[u])); }
void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	t -= s[v];
	p[u] = v;
	s[v] = s[v] ^ s[u];
}
int main() {
	int n, m, i, j, dy[] = { 0,0,1,-1 }, dx[] = { 1,-1,0,0 }, D, y, x, ty, tx;
	priority_queue<_q> pq;
	scanf("%d%d", &n, &m);
	vector<vector<bool>> used(n, vector<bool>(m, false));
	for (i = 0; i < n; i++) for (j = 0; j < m; j++) {
		p[i*m + j] = i * m + j;
		scanf("%d", &D);
		pq.push(_q{ D, i * m + j });
	}
	while (!pq.empty()) {
		_q u = pq.top(); pq.pop();
		D = u.D, y = u.v / m, x = u.v % m;
		used[y][x] = 1;
		s[y*m + x] = D;
		for (i = 0; i < 4; i++) {
			ty = y + dy[i], tx = x + dx[i];
			if (0 <= ty && ty < n && 0 <= tx && tx < m && used[ty][tx])
				merge(y*m + x, ty*m + tx);
		}
		t += s[find(y*m + x)];
		ans = ans > t ? ans : t;
	}
	printf("%lld", ans);
	return 0;
}