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

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

1091번: 카드 섞기

문제

지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번)

일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런 식으로 카드를 나누어 준다. 하지만, 지민이는 약간 사기를 치려고 한다.

지민이는 처음에 카드를 섞기 전에 카드의 순서를 알고 있고, 이 정보를 이용해 각 카드가 특정한 플레이어에게 보내지게 할 것이다.

카드를 한 번 섞을 때는 주어진 방법을 이용해서만 섞을 수 있고, 이 방법은 길이가 N인 수열 S로 주어진다. 카드를 한 번 섞고 나면 i번째 위치에 있던 카드는 S[i]번째 위치로 이동하게 된다.

각 카드가 어떤 플레이어에게 가야 하는지에 대한 정보는 길이가 N인 수열 P로 주어진다. 맨 처음 i번째 위치에 있던 카드를 최종적으로 플레이어 P[i] 에게 보내야 한다.

지민이가 목적을 달성하기 위해 필요한 카드 섞는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 3보다 크거나 같고, 48보다 작거나 같은 3의 배수이다.

둘째 줄에 길이가 N인 수열 P가 주어진다. 수열 P에 있는 수는 0, 1, 2 중 하나이다.

셋째 줄에 길이가 N인 수열 S가 주어진다. 수열 S에 있는 수는 모두 N-1보다 작거나 같은 자연수 또는 0이고 중복되지 않는다.

출력

첫째 줄에 몇 번 섞어야 하는지 출력한다. 만약, 섞어도 섞어도 카드를 해당하는 플레이어에게 줄 수 없다면, -1을 출력한다.

---

문제가 012012012... -> P로 가는 것이 아니라 P->012012012 가 되어야 한다. 다른 블로그들을 보니 사이클은 무조건 생기므로 초기의 상태가 돌아오면 반복문을 그만 하는 것으로 풀었다. 하지만 나는 사이클들의 주기를 파악해서 그 주기들의 최소공배수가 모든 카드의 주기이므로 반복문을 그 횟수만큼 돌렸다. 

Disjoint set을 이용하여 서로 다른 사이클들을 파악한다. 그다음 서로 다른 set 들의 원소 개수를 구하는데 원소의 개수가 사이클의 주기이다. 이 주기들의 최소공배수를 구하여 카드를 섞기 시작한다. 섞고 난 다음 카드의 주인이 012012.. 의 순이라면 섞은 횟수를 반환한다.

#include <iostream>
#include <queue>

using namespace std;
int P[48] = { 0 };
int S[48] = { 0 };
int parent[48] = { 0 };
int N;

int Find(int x) {
	if (x == parent[x]) return x;
	return x = Find(parent[x]);
}


void Union(int a, int b) {
	int x = Find(a);
	int y = Find(b);
	if (x == y) return;
	else {
		parent[y] = x;
	}
	return;
}

int gcd(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

int solve() {
	int vis = 0,cnt = 0;
	int group[48] = { 0 };
	for (int i = 0; i < N; i++) {
		int j = Find(i);
		if (!(vis & (1 << j))) {
			vis = vis | (1 << j);
		}
		group[j]+=1;
	}
	//규칙성 구하기
	int reg = 1;
	bool flag = false;
	for (int i = 0; i < N; i++) {
		if (group[i]) {
			reg = lcm(reg, group[i]);
		}
	}

	for (int i = 0; i < N; i++) {
		if (P[i] != (i % 3))
			break;
		if (i == N - 1) return 0;
	}
	for (int k = 1; k < reg; k++) {
		flag = true;
		int tmp[48];
		for (int i = 0; i < N; i++) {
			tmp[S[i]] = P[i];
		}
		for (int i = 0; i < N; i++) {
			P[i] = tmp[i];
			if (P[i] != (i % 3))
				flag = false;
		}
		
		if (flag)
			return k;

	}
	return -1;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		parent[i] = i;
		cin >> P[i];
	}
	for (int i = 0; i < N; i++) {		
		cin >> S[i];
		Union(i, S[i]);
	}
	
	cout << solve();
}

---

처음에 012012... -> P로 가는 줄 알았는데 알고 보니 반대였다. 문제의 질문 게시판에 나와 비슷하게 이해를 못 한 사람들이 많은 것 같아 조금 위안이 되었다. 여러 번 읽고 이해하고 나니 뜻이 이해가 되었다.

정석적인 코드와 내 코드의 차이는 매번 초기 상태와 같은 지 확인하기 vs 처음에 주기를 딱 한번 확인하고 그보다 넘게 돌았다면 안된다고 반환하기인것 같다. 이 방법이 작성해야할 코드가 많긴 해도 시간복잡도 상으로는 우수할 것 같다. 하지만 문제에서는 N의 최댓값이 48이고 시간제한도 2초여서 시간복잡도의 차이로 성공과 실패가 갈리지는 않는 것 같다. 사이클이 있으면 주기를 굳이 구하지 않아도 초기상태와 비교하여 사이클을 파악할 수 있다는 것을 인지해두면 좋을 것 같다!