푸는 방법이 다소 다양해서 포스팅하고자 한다.
주어진 문제에서 보면 최대 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;
}