BOJ 34072 배열 정리하기

문제 링크입니다.

문제 요약

순열을 올린 $50 \times 50$ 크기 이내의 정사각 배열이 주어집니다. 주어진 연산

• 가로로 붙어 있는 두 수 중 하나에 나머지 수를 더하거나 빼기
• 세로로 붙어 있는 두 수 중 하나에 나머지 수를 XOR하기

를 $400\,000$번 이내로 수행해 배열을 정렬하세요.

풀이

제한 내에서 도는 풀이가 여러 가진데, 그중 제 풀이는 다음과 같은 과정을 거쳐 배열을 정렬합니다.

1. 0을 이용한 수 이동
2. 대부분의 수를 0으로 초기화 (normalize)
3. $1$과 $N$을 이용해 배열의 모든 값을 재구성 (construct)

0. 0을 이용한 수 이동

이 문제에서 가장 어려운 부분은 수를 원하는 대로 가로로 옮기기가 상당히 까다롭다는 점입니다. XOR을 통해 두 수를 swap하는 방법은 잘 알려져 있지만, 덧셈 뺄셈의 경우는 swap 이후 한쪽의 부호가 반대로 뒤집힌다는 문제점이 있기 때문입니다.

그러나 둘 중 한 수가 0이라면 이렇게 부호가 뒤집히는 경우를 신경쓰지 않아도 되고, 가로세로 모든 방향에서 연산 횟수를 더 적게 써서 수를 옮길 수 있습니다. 정확히는 0은 모든 방향으로 연산 2번에 이동할 수 있습니다.

1. normalize

만약 수가 N x 1 의 순서로 나열되어 있다면 우리는 x 를 $\lceil { {3 \over 2} N} \rceil$번의 연산으로 0으로 만들 수 있습니다.

따라서 우리는 처음에 0을 찾아 이동 수단으로 활용해 1과 N을 위와 같은 형태로 붙여 주고, 나머지 수들을 BFS 순서대로 x 위치로 끌고 와서 0으로 바꿔주는 작업을 반복하면 됩니다. 이 과정에서 x 로 끌려오는 경로 상의 수는 항상 모두 0이므로 빠르게 수를 옮겨줄 수 있습니다.

2. construct

1단계에서 N x 1 꼴을 오른쪽 위 구석에 만들어주었다면, 0 N 1 꼴로 한 번 자리를 바꿔서 만들어 주고 2단계를 바로 진행할 수 있습니다.

$A[i][j] = i\times N + j$로 만들어야 합니다. 이를 위해 먼저 $A[i][0]$을 $i \times N$으로 채우고, $A[i][j]\ (j\neq 1)$를 $j$로 채우면 됩니다. 누적 합 비슷한 아이디어를 사용하면 이를 매우 적은 연산 (~15000회) 으로 구현할 수 있습니다.

위의 내용을 잘 구현하면 최악의 경우에 약 $395\,000$번 정도 연산을 쓰는 프로그램을 짤 수 있습니다. 화이팅!

코드

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
int n, a[55][55]; bool vis[55][55];
vector<int> ans;
queue<int> que;

inline void q(int op, int x, int y){
	ans.push_back(op<<12|x<<6|y); if(op == 1) a[x][y] += a[x][y+1];
	if(op == 2) a[x][y] -= a[x][y+1];
	if(op == 3) a[x][y] += a[x][y-1];
	if(op == 4) a[x][y] -= a[x][y-1];
	if(op == 5) a[x][y] ^= a[x+1][y];
	if(op == 6) a[x][y] ^= a[x-1][y];
}

inline void L(int x, int y){q(1,x,y-1); q(4,x,y);}
inline void R(int x, int y){q(3,x,y+1); q(2,x,y);}
inline void U(int x, int y){q(5,x-1,y); q(6,x,y);}
inline void D(int x, int y){q(6,x+1,y); q(5,x,y);}
inline void R0(int x, int y){q(1,x,y); q(4,x,y+1);}
inline void L0(int x, int y){q(3,x,y); q(2,x,y-1);}
inline void D0(int x, int y){q(5,x,y); q(6,x+1,y);}
inline void U0(int x, int y){q(6,x,y); q(5,x-1,y);}
inline void u(int x, int y){q(5,x-1,y); q(6,x,y); q(5,x-1,y);}
inline void pull(int x, int y){
	if(x == 0) D(x++, y);
	while(y < n-2) R(x, y++);
	while(y > n-2) L(x, y--);
	while(x) U(x--, y);
}

inline void print_qry(){
	cout << ans.size() << '\n';
	for(int& i : ans) cout << (i>>12) << ' ' << ((i>>6)&63) << ' ' << (i&63) << '\n';	
}

void solve2(){
	while(a[0][0] != 0 || a[0][1] != 1){
		if(a[0][0] == 0) R0(0,0);
		else if(a[0][1] == 0) D0(0,1);
		else if(a[1][1] == 0) L0(1,1);
		else if(a[1][0] == 0) U0(1,0);
	}
	if(a[1][0] == 3){D0(0,0); R0(1,0); u(1,0); L0(1,1); U0(1,0);}
}

void normalize(){
	//push 0 to top : ~2n
	bool z = 0; int zj;
	for(int i = 0; i < n && !z; i++) for(int j = n-1; j >= 0 && !z; j--) if(a[i][j] == 0){
		for(int ii = i; ii > 0; ii--) U0(ii, j); //2n
		zj = j; z = 1;
	}

	//push 1 to top : ~13n
	bool o = 0; int oj;
	for(int j = n-1; j >= 0 && !o; j--) for(int i = 0; i < n && !o; i++) if(a[i][j] == 1){
		for(int ii = i; ii > 0; ii--) u(ii, j); //3n
		oj = j; o = 1;
		if(oj == zj){ //4
			if(oj == n-1){L0(1,zj--); U0(1,zj);}
			else{R0(1,zj++); U0(1,zj);}
		}
	}
	while(zj > oj-1){L0(0,zj); zj--; if(oj == zj) oj++;}
	while(zj < oj-1){R0(0,zj); zj++;}
	while(zj+1 == oj && oj != n-1){
		D0(0,zj); R0(1,zj++); R0(1,zj++); U0(1,zj); L0(0,zj--); oj++; //10n
	}
	
	//push n to top : ~13n
	bool nb = 0; int nj;
	for(int j = n-1; j >= 0 && !nb; j--) for(int i = 0; i < n && !nb; i++) if(a[i][j] == n){
		for(int ii = i; ii > 1; ii--) u(ii, j); //3n;
		if(i == 0) u(1, j);
		nj = j; nb = 1;
		//need help with zero... move it to n-3th col
		if(nj == n-1){
			D0(0,zj); R0(1,zj++); D0(1,zj); L0(2,zj--); L0(2,zj--); U0(2,zj); R0(1,zj++); U0(1,zj); u(1,n-3);
		}
		else if(nj == n-2){
			D0(0,zj); L0(1,zj--); U0(1,zj); R0(0,zj++);
		}
		else{
			while(zj > nj+1) L0(0,zj--); D0(0,zj);
			while(nj < n-3){L0(1,zj--); nj++; D0(1,zj); R0(2,zj++); R0(2,zj++); U0(2,zj);} //10n
			U0(1,zj); u(1,nj);
		}
	}
	// from above about ~30n = ~1500

	que.push(0); que.push(n-2); vis[0][n-3] = vis[0][n-2] = vis[0][n-1] = 1;
	while(que.size()){ //flood fill
		int x = que.front(); que.pop(); int y = que.front(); que.pop();
		for(int dir = 0; dir < 4; dir++){
			int nx = x+dx[dir], ny = y+dy[dir];
			if(nx < 0 || ny < 0 || nx >= n || ny >= n || vis[nx][ny]) continue;
			que.push(nx); que.push(ny); vis[nx][ny] = 1;
		}
		if(!a[x][y]) continue;
		pull(x, y);
		while(a[0][n-2] >= n) q(4,0,n-2);
		if(n-a[0][n-2] < a[0][n-2]) q(4,0,n-2);
		while(a[0][n-2] < 0) q(1,0,n-2);
		while(a[0][n-2] > 0) q(2,0,n-2);
	} //2500*(100+50/2+25) : ~375000...maybe??
	R(0,n-3);
}

void construct(){
	for(int j = n-3; j >= 0; j--) q(1,0,j); //n
	for(int j = n-3; j >= 0; j--) q(1,0,j); //n
	for(int i = n-1; i >= 1; i--){ 
		for(int j = n-1-i; j > 0; j--) L(0,j); //2n^2
		for(int ii = 0; ii < i; ii++) D(ii,0); //2n^2
	}
	for(int j = n-2; j >= 1; j--) q(1,0,j); //n
	for(int i = 1; i < n; i++) for(int j = 1; j < n; j++) q(6,i,j); //n^2
	for(int i = 0; i < n; i++) for(int j = 1; j < n; j++) q(3,i,j); //n^2
	//6n^2+3n ~= 15000
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); ans.reserve(404040);
	cin >> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> a[i][j];
	if(n == 2) solve2();
	else{normalize(); construct();}
	print_qry();
}