BOJ 2549 - 루빅의 사각형

* BOJ 2549 - 루빅의 사각형

  [ 분류 - BFS(Bidirectional search)/ Backtracking ]

  푸는 방법이 다소 다양해서 포스팅하고자 한다.

  주어진 문제에서 보면 최대 7번까지만 움직여도 충분히 해결가능한 입력만 주어진다고 한다. 그렇다면 주어진 입력과 목표 4x4배열을 E와 S라고 하자. 그러면 E가 최대 3~4번, S가 최대 3~4번을 움직이면 그 안에 겹치는 교차지점이 반드시 생긴다.

  특정 지점 4x4 배열 k에 대해 움직일 수 있는 가지수는 (4+4)*3이 된다. 즉 24 가지수가 나올 수 있는데, S또는 E에서 최대 7번을 움직이기 때문에 24^7의 경우의 수가 나오는데 이 값은 너무나 크다. 시간초과가 자명하다.

  따라서 S,E가 교차지점까지 3~4번 이동하는 최대 2*(24^4)의 경우의 수로 승부를 보자. 양방향 탐색을 구현해주시면 되겠다. 백트랙킹도 가능하나 이 포스팅은 양방향 탐색이 가능함을 알리기 위한 포스팅이기에 다른 블로그를 참고해주길 바란다.

#include <cstdio>
#include <queue>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
using namespace std;
struct _d { int type, i, k; };
void rotH(vector<vector<int>>& board, int rp) {
	int t = board[rp][3];
	for (int i = 3; i > 0; i--)
		board[rp][i] = board[rp][i - 1];
	board[rp][0] = t;
}

void rotW(vector<vector<int>>& board, int cp) {
	int t = board[3][cp];
	for (int i = 3; i > 0; i--)
		board[i][cp] = board[i - 1][cp];
	board[0][cp] = t;
}

map<vector<vector<int>>, pair<int, _d>> chk;
map<vector<vector<int>>, vector<vector<int>>> from;
void addingChk(vector<vector<int>>& u, vector<vector<int>>& v, int dis, int isR, int idx, int cnt) {
	chk.insert({ v,{ dis, _d{ (isR ? 2 : 1), idx, (dis ? 4 - (cnt+1) : (cnt+1)) } } });
	from.insert({ v,u });
}

int main() {
	int dis;
	_d mid;
	deque<_d> r;
	vector<vector<int>> s(4, vector<int>(4)), u, v, ans(4, vector<int>(4)), fr, en;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++) {
			scanf("%d", &s[i][j]);
			ans[i][j] = i * 4 + j + 1;
		}
	queue<pair<vector<vector<int>>, int>> q;
	q.push({ s,0 });
	q.push({ ans, 1 });
	int i, j, k, qsize, cnt = 0, f = 1;
	from.insert({ s, s });
	from.insert({ ans, ans });
	chk.insert({ s,{ 0, _d{} } });
	chk.insert({ ans,{ 1, _d{} } });
	while (!q.empty() && f) {
		qsize = (int)q.size();
		while (qsize-- && f) {
			u = q.front().first, dis = q.front().second, q.pop();

			for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) {
				v = u;
				for (k = 0; k < 3 && f; k++) {
					rotH(v, i);
					auto it = chk.find(v);
					if (it != chk.end() && it->second.first != dis) {
						f = 0;
						fr = u, en = it->first;
						mid = _d{ 1, i, (dis ? 4 - (k+1) : (k + 1)) };
					}
					else if (it == chk.end()) {
						addingChk(u, v, dis, 0, i, k);
						q.push({ v, dis });
					}
				}

				v = u;
				for (k = 0; k < 3 && f; k++) {
					rotW(v, j);
					auto it = chk.find(v);
					if (it != chk.end() && it->second.first != dis) {
						f = 0;
						fr = u, en = it->first;
						mid = _d{ 2, j, (dis ? 4 - (k + 1) : (k + 1)) };
					}
					else if (it == chk.end()) {
						addingChk(u, v, dis, 1, j, k);
						q.push({ v, dis });
					}
				}
			}
		}
	}

	if (dis) swap(fr, en);	
	while (fr != from[fr]) {
		r.push_front(chk[fr].second);
		fr = from[fr];		
	}
	r.push_back(mid);
	while (en != from[en]) {
		r.push_back(chk[en].second);
		en = from[en];
	}

    printf("%d\n", (int)r.size());
	while (!r.empty()) {
		_d x = r.front(); r.pop_front();
		printf("%d %d %d\n", x.type, x.i + 1, x.k);
	}
	return 0;
}