[백준 1327] 소트 게임 (C++)

https://www.acmicpc.net/problem/1327

1327번: 소트 게임

문제

---

홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집어야 한다. 예를 들어, 순열이 5 4 3 2 1 이었고, 여기서 K가 3일 때, 4를 뒤집으면 5 2 3 4 1이 된다. 반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다.

입력으로 들어온 순열을 오름차순으로 만들려고 한다. 게임을 최대한 빨리 끝내고 싶을 때, 수를 최소 몇 개 선택해야 하는지 구해보자.

 

입력

---

첫째 줄에 순열의 크기 N과 K가 주어진다. 둘째 줄에 순열에 들어가는 수가 주어진다.

 

출력

---

첫째 줄에 정답을 출력한다. 만약 오름차순으로 만들 수 없으면 -1을 출력한다.

 

제한

---

• 2 ≤ K ≤ N ≤ 8

문제 풀이

---

bfs 문제.

순열을 문자열로 바꾸어 큐에 저장하고, 방문 여부를 확인하기 위해 set에 이미 만들어져서 탐색한 순열들을 저장해놓는다. 그리고 큐의 원소들을 하나씩 너비 우선 탐색하며 해당 순열이 오름차순인지 확인한다.

 

아래는 코드.

내 풀이는 set에만 순열을 문자열로 바꾸어 확인했지만 큐도 순열을 문자열로 바꾸어 저장하면 더 메모리를 절약할 수 있을 것이다.

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int num;
	bool isFound = false;
	cin >> N >> M;
	vector<int> v;
	vector<int> answerV;
	queue<pair<vector<int>, int>> notUsed;
	set<string> s;
	set<string>::iterator it;
	string str = "";
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		v.push_back(num);
		answerV.push_back(i + 1);
		str += v.at(i)+48;
	}
	notUsed.push(make_pair(v, 0));
	s.insert(str);
	while (!notUsed.empty())
	{
		pair<vector<int>, int> current = notUsed.front();
		if (current.first == answerV)
		{
			cout << current.second << "\n";
			isFound = true;
			break;
		}
		vector<int> nextV = current.first;
		for (int i = 0; i < N - M + 1; i++)
		{
			nextV = current.first;
			str = "";
			reverse(nextV.begin() + i, nextV.begin() + i + M);
			for (int j = 0; j < N; j++)
			{
				str += nextV.at(j)+48;
			}
			it = s.find(str);
			if (it == s.end())
			{
				s.insert(str);
				notUsed.push(make_pair(nextV, current.second + 1));
			}
		}
		notUsed.pop();
	}
	if (isFound == false)
	{
		cout << "-1" << "\n";
	}
	return 0;
}