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

문제 링크

1091번: 카드 섞기

문제 요약

0부터 N-1까지의 카드가 있고, 0, 1, 2 세 명의 플레어어가 있다. 이 카드를 섞을 것인데, 섞는 방법은 S라는 수열로 주어진다. 한번 섞으면 i번째 카드는 S[i]번째 위치로 이동하게 된다. 그리고 P라는 수열이 주어지는데, 이 수열은 i번 카드를 플레이어 P[i]가 가지고 있어야 함을 의미한다. 이때 카드 섞는 횟수의 최솟값을 구해야 한다. 단, 반복해도 불가능한 경우에는 -1을 출력해야 한다.

접근 방법

사실 구현과 시뮬레이션 자체는 그렇게 어렵지 않은데, 반복해도 불가능한 경우에 -1을 출력하는 것이 어려울 것이라고 생각됩니다. 언제까지 반복을 해야할지를 생각해야 합니다.

풀고 나서 난이도 기여를 보니까, 순열 사이클 분할을 이용해서 많이 푸신거 같습니다. '순열 주기는 순열에 존재하는 각각의 순열 사이클의 길이의 최소공배수와 같다.'는걸 이용해서 최대횟수를 구하고, 그만큼만 반복하면 되는 풀이라고 합니다. 저도 난이도 기여를 보고 구글링해서 알게 되었습니다.

제 경우에는 저걸 모른채 std::set에 std::vector를 저장하는 방식으로 풀었습니다. 이 풀이도 꽤 여유있게 AC를 받는거 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> s, p, v1, v2;
set<vector<int>> visited;

void func(vector<int>& v1, vector<int>& v2)
{
	for (int i = 0; i < n; i++)
		v2[s[i]] = v1[i];
}

int check(vector<int>& v)
{
	int flag = 1;
	for (int i = 0; i < n; i++)
	{
		if (i % 3 != p[v[i]])
		{
			flag = 0;
			break;
		}
	}

	if (visited.find(v) == visited.end())
		visited.insert(v);
	else
		flag = 2;

	return flag;
}

int main(void)
{
	cin >> n;

	s.resize(n);
	p.resize(n);
	v1.resize(n);
	v2.resize(n);

	for (int i = 0; i < n; i++)
		cin >> p[i];

	for (int i = 0; i < n; i++)
		cin >> s[i];

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

	int cnt = 0;
	bool flag = false;
	while (1)
	{
		int tmp = 0;
		if (!flag)
		{
			tmp = check(v1);			
			func(v1, v2);
		}
		else
		{
			tmp = check(v2);
			func(v2, v1);
		}

		if (tmp >= 1)
		{
			if (tmp == 2)
				cnt = -1;
			break;
		}

		flag = !flag;
		cnt++;
	}

	cout << cnt;
	return 0;
}