Algospot - 정렬 게임(SORTGAME)

* Algospot - 정렬 게임(SORTGAME, )

  [ 분류 - BFS ]

간단한데, 이상하게 자꾸 시간초과가 뜨는 문제다.

* 접근 방법

  1. 길이가 x인 수열을 한 번 이상의 연산을 수행했을 때, 정렬 결과로 나올 수 있는 경우의 수는 x!이다.

  2. 내부에서 연산을 수행하는 속도는 약 O(x)다. 따라서 1.의 결과로 보면 속도는 최대 8!*8이다.

  3. 하지만 이를 들어오는 쿼리마다 수행할 수는 없으므로 "미리" 저장을 해놓고 들어오는 입력에 따라 O(C lg(x!*x)) 시간으로 찾을 수 있도록 한다.

  4. 최대가 8이므로 길이 8짜리만 구하고, 나머지 길이에 대해서는 남는 부분을 오름차순으로 채우고 찾으면 된다.

- 코드

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
	int C, N, D, cnt, i, j, k, cur = 0, sz, u, v, pow10[10] = { 1 }, t = 0, a, b;
	for (i = 1; i < 10; i++) pow10[i] = pow10[i - 1] * 10;
	queue<int> q;
	map<int, int> vi;
	for (i = 1; i <= 8; i++) {
		t *= 10;
		t += i;
	}
	q.push(t);
	vi[t] = 0;
	while (!q.empty()) {
		sz = q.size();
		cur++;
		while (sz--) {
			u = q.front(), q.pop();
			for (i = 0; i < 8; i++) {
				for (j = i + 1; j < 8; j++) {
					v = u;
					for (k = 0; k < (j - i + 1) / 2; k++) {
						a = (v / pow10[i+k]) % 10;
						b = (v / pow10[j-k]) % 10;
						v -= a * pow10[i+k] + b * pow10[j-k];
						v += b * pow10[i+k] + a * pow10[j-k];
					}
					if (vi.count(v) == 0) {
						vi[v] = cur;
						q.push(v);
					}
				}
			}
		}
	}
	vector<int> sorted(8);
	scanf("%d", &C);
	while (C--) {
		scanf("%d", &N);
		vector<int> vt, origin;
		for (i = 0, cnt = 1; i < N; i++, cnt++) {
			scanf("%d", &D);
			vt.push_back(D);
		}
		for(i=0;i<8;i++) sorted[i] = i + 1;
		origin = vt;
		sort(vt.begin(), vt.end());
		for (i = 0; i < N; i++) for (j = 0; j < N; j++) {
			if (origin[i] == vt[j]) {
				sorted[i] = j + 1;
				break;
			}
		}
		u = 0;
		for (int& s : sorted) {
			u *= 10;
			u += s;
		}
		printf("%d\n", vi[u]);
	}

	return 0;
}