문제
중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.

정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.

입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 1000) 이 주어진다. 각 테스트 케이스의 첫 줄에는 수열의 길이 N (1 <= N <= 8) 이 주어진다. 다음 줄에 N개의 정수로 각 수열의 원소들이 순서대로 주어진다. 한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수이다.

출력
각 테스트 케이스마다 입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력한다.

예제 입력
3
8
1 2 3 4 8 7 6 5
4
3 4 1 2
3
1 2 3

예제 출력
1
2
0

🤔생각

"이게 왜 BFS문제지?"라는 생각이 들었다. 그래프로 접근할 생각이 떠오르지 않았기 때문이다.

👏코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>

using namespace std;

map<vector<int>, int> toSort;

void precalc(int n) {
	vector<int> perm(n);
	queue<vector<int>> q;

	for (int i = 0; i < n; i++)
		perm[i] = i;

	q.push(perm);
	toSort[perm] = 0;

	while (!q.empty()) {
		vector<int> here = q.front();
		q.pop();

		int cost = toSort[here];

		for (int i = 0; i < n; i++) {
			for (int j = i + 2; j <= n; j++) {
				reverse(here.begin() + i, here.begin() + j);
				if (toSort.count(here) == 0) {
					toSort[here] = cost + 1;
					q.push(here);
				}
				reverse(here.begin() + i, here.begin() + j);
			}
		}
	}
}

int solve(const vector<int>& perm) {
	int n = perm.size();
	vector<int> fixed(n);

	for (int i = 0; i < n; i++) {
		int smaller = 0;
		for (int j = 0; j < n; j++)
			if (perm[i] > perm[j])
				smaller++;
		fixed[i] = smaller;
	}

	return toSort[fixed];
}

int main(void) {
	int C, N, tmp;
	vector<int> v;

	cin >> C;

	precalc(8);

	while (C--) {
		cin >> N;

		for (int i = 0; i < N; i++) {
			cin >> tmp;
			v.push_back(tmp);
		}
		int k = 1000001;
		while(v.size() < 8)
			v.push_back(k++);
		
		cout << solve(v) << endl;
		v.clear();
	}
	return 0;
}

🤔후기

수열 전체를 그래프에 대응 시킬생각을 하지 못했었다. 여태까지 풀어봤던 문제들은 어떤 수 하나만이 그래프에 대응되었기 때문이다. 아무래도 자유로운 시각을 갖지 못하고 고정관념이 생겼던거 같다. 그리고 수열을 상대적 크기로 고정 시켜도 정렬을 수행하는데는 차이가 없다는 들으면 당연한 사실을 생각해내지 못했었다.