[c++/백준] 1091번: 카드 섞기

문제 링크

1091번: 카드 섞기

풀이

문제 해석을 잘못해서 조금 헤맸던 문제

1. Shake()함수에서 카드를 섞도록 한다.
   1-1. tmp[S[i]] = arr[i];
   1-2. 한 번 섞을 때마다 answer++
2. 섞인 카드가 원하는 대로 가는지 확인하는 함수 Check()
   2-1. P[arr[i]] != i%3 일 경우는 제대로 주어지지 않는다는 뜻이므로 false 리턴
3. Check()가 true 될 때까지 Shake() 하는데,
   3-1. 이미 한 번 나온 카드 순서(arr)가 또 나올 경우, 계속 해도 원하는 카드의 순서가 안나온다는 의미
   3-2. 이 것의 체크는 set으로 한다.
   3-3. set에 있으면 -1 리턴, 없으면 set에 insert

코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n;
vector<int> P;
vector<int> S;
vector<int> arr;
int answer = 0;

set<vector<int>> order;

bool Check()
{
	for (int i = 0; i < n; i++)
	{
		if (P[arr[i]] != i%3) return false;
	}
	return true;
}

void Shake()
{	
	if (Check())
	{
		cout << answer << endl;
		return;
	}

	vector<int> tmp(n);
	for (int i = 0; i < n; i++) // 섞기
	{
		tmp[S[i]] = arr[i];
	}
	arr = tmp;

	if (order.find(arr) != order.end()) // 이미 검사한 카드 순서라면
	{
		cout << -1 << endl;
		return;
	}
	order.insert(arr);

	answer++;

	Shake();
}

int main(void)
{
	cin >> n;

	P.resize(n);
	S.resize(n);

	for (int i = 0; i < n; i++)
	{
		cin >> P[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> S[i];
	}
	
	arr.resize(n);
	for (int i = 0; i < n; i++)
	{
		arr[i] = i;
	}

	Shake();

	return 0;
}