[스프라그 그런디 정리] - BOJ_11868 : 님 게임 2

저번 포스팅에 이어, 이번에도 게임 이론에 대해 공부해보겠다.

2023.05.09 - [PS] - [게임 이론] - BOJ_11062 : 카드 게임

이번에는 boj 11868번을 풀면서 스프라그 그런디 정리에 대해 배워보자.

문제의 아이디어 자체는 길지 않다. 여러개의 돌 무더기가 있고, 두 사람은 돌 무더기중 하나를 선택해, 그 돌무더기에서 하나 이상의 돌을 제거할 수 있다. 그리고 전체 돌 더미에서 마지막 돌을 가져가는 사람이 승리하는 것이 게임 조건이다.

이 문제 역시 게임 이론을 근거로 하기에, 두 사람 모두 최적의 플레이를 한다고 가정한다.

즉, 승자가 정해져 있는것이다.

이 문제에서는 스프라그 그런디 정리라는 알고리즘을 알고 있어야한다.

💡스프라그-그런디 정리란?

게임판의 상태를 각각 하나의 자연수 (그런디 수)로 치환할 수 있다는 것이 스프라그-그런디 정리이다.

그런디 수는 다음과 같이 정해진다.

1. 패배하게 되는 그런디 수는 0다.
2. 어떤 게임판의 상태 x에서 이동할 수 있는 다른 상태들의 그런디 수의 집합 Y에 대해, 이 게임판의 그런디 수는 $mex(y)$다.

그리고, $mex(y)$는 y에 속하지 않는 자연수 중 가장 작은 값이다.

ex) 만약 x에서 이동할 수 있는 위치가 3개고, 각 위치의 그런디 수가 0,1,3이라면, mex(y)는 2이다.

index	0	1	2	3	4	5	6	7	8
승패	lose	win	win	win	lose	win	win	win	lose
그런디 수	0	1	2	3	0	1	2	3	0

 

만약 내가 게임판에서 제외할 수 있는 돌의 개수가 1,2,3중 하나만을 선택해야 한다면, 돌이 9개 있는 게임판에서의 그런디 수는 위 표와 같이 나타낼 수 있다.

그리고 그런디 수가 같은 두 게임판의 상태는 사실상 같은 상태임을 나타낸다.

따라서 그런디 수가 0인 상태는 무조건 패배하는 상태이며, 이 문제에서의 게임은 돌을 원하는 개수 만큼 뺄 수 있기에, 0보다 큰 상태에서는 한 번의 행동으로 무조건 그런디 수가 0인 상태로 만들 수 있으므로 승리할 수 있는 상태라고 볼 수 있다.

index	0	1	2	3	4	5	6	7	8
승패	lose	win	win	win	win	win	win	win	win
그런디 수	0	1	2	3	4	5	6	7	8

이 그런디 수는, 게임판이 한개 일때는 크게 의미가 없고 (dp로 문제 해결이 충분히 가능하므로) 게임판이 여러 개일 때 유용하게 사용가능하다.

예를 들어, 현재 n개의 게임판이 있고, 각 게임판의 그런디 수가 $g(i)$라고 해보자.

이 n개의 게임을 동시에 진행한다면, 현재 상태의 그런디 수는$ g1⊕g2⊕⋯⊕⋯⊕gn$이 된다.

이때  $g1⊕g2⊕⋯⊕⋯⊕gn=0$ 이라면 선공 플레이가 패배하고 그렇지 않으면 승리한다.

 

👀증명 단계

먼저 xor의 몇가지 특징을 짚고 넘어가자.

• 결합법칙: (a ⊕ b) ⊕ c= a ⊕ (b⊕ c)
• 교환법칙: (a ⊕ b)= (b ⊕ a)
• Identity: (0 ⊕ a)= a
• Self-inverse: (a ⊕ a)= 0

이 문제를 풀기 전 몇가지 가정을 하겠다.

 

움직이기 전 모든 더미의 그런디수를 $a_1,a_2,a_3,...a_n$이라 하고,

움직이기 전 모든 더미의 그런디수를 $b_1,b_2,b_3,...b_n$이라 하자.

이때, 변화가 일어난 한 더미를 k번째 더미라고 한다면,

$a_k$ -> $b_k$ 의 변화 이외의 나머지 더미는 그런디수가 그대로 $a_i$ 상태일 것이다.

 

$s=a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_N$, $t=b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_N$, 이라고 할때 다음을 만족한다.

$ t=0 \oplus t \\ =(s \oplus s) \oplus t \\ =s \oplus (s \oplus t ) \\ =s \oplus ( (a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_N) \oplus ( b_2 \oplus b_3 \oplus b_4 \oplus b_N) ) \\ =s \oplus((a_1 \oplus b_1) \oplus (a_2 \oplus b_2) \oplus (a_3 \oplus b_3) \oplus (a_N \oplus b_N)) \\ =s \oplus( 0\oplus 0\oplus 0\oplus 0\oplus (a_k\oplus b_k) \oplus 0 \oplus 0) \\=s \oplus ( a_k \oplus b_k) $

 

1.$s=0$이면 $t \ne 0$ 이다

귀류법을 통해 증명

$s=0$ 이 $t = 0$ 이라 한다면 $a_k \oplus b_k =0$이다. (a_k \oplus b_k가 1일경우, t또한 1이 되므로)

$ a_k=a_k \oplus 0 \\ = a_k \oplus(a_k \oplus b_k) \\= (a_k \oplus a_k) \oplus b_k \\=b_k $

 

따라서 $a_k=b_k$이다. 그런데 이는 $k$에 대한 가정에 대한 모순이다. ($a_k -> b_k$가 되는 과정에선 반드시 변화가 일어나야 하므로!)

따라서 아래와 같은 사실이 자명하다.

$$ t=s \oplus (a_k \oplus b_k) \\= 0 \oplus (a_k \oplus b_k) \\=a_k \oplus b_k \\ \ne 0 $$

 

2. $s\ne 0$ 이면 $t=0$을 반드시 만들 수 있는 경우가 존재한다.

bit의 관점에서 볼때, $s$보다 크지않은 가장 큰 $2^k$가 존재하고 $2^k$ 를 가지고 있는 $a_i$가 적어도 하나존재한다. (a의 모음을 xor 했을 때 비트가 1이 되었다는건, 해당 위치 비트를 가진 $a_i$가 존재한다는 뜻이므로.)

$b_i$는 $2^k$으로 부터 감소된 값이고, $2^{k-1} +2^{k-2}+2^{k-3}+...+2^0=2^{k}-1$이므로 더 작은 값들에 대하여 $b_i =s \oplus a_i$ 가 만족하도록 할 수 있다.

$ t= s \oplus (a_i \oplus b_i) \\= s \oplus (a_i \oplus (s \oplus a_i)) \\ =(s \oplus s) \oplus (a_i \oplus a_i) \\ =0 $

따라서 $t=0$으로 반드시 만들수 있고 공을 마지막으로 가져가는 경우 $t=0$이므로 반드시 승리하는 경우가 존재한다.

 

 

이제 문제를 다시 생각해보자.

플레이어들은 항상 최적의 경우의 수를 알기 때문에, s 상태에서 t 상태로 상태를 변경할때 위 증명과 같이

$s\ne 0$ 이면 $t=0$ 상태로 "반드시" 만들 수 있다.

즉, 상대가 패배하는 경우로 반드시 게임을 진행시킬 수 있다는 것이다.

반대로, 상대는 $s=0$이면 $t \ne 0$ 이므로, 게임을 지는 경우의 수를 받았을 때,

그런디 수가 0이 아닌값으로 게임을 넘길 수 밖에 없는 것이다.

따라서, 게임을 시작했을 때 전체 그런디 수를 XOR 한 t가 $ t \ne 0$ 이면 승리하고 $t=0$이면 패배한다(자신의 차례에 0을 만들어야하기에..)

 

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

11868번: 님 게임 2

 

이제 문제를 풀어보자.

너무나도 간단하다. 처음 조건을 받았을 때, 각 더미의 그런디 수를 XOR 해주고, 0인지 0이 아닌지만 판별해주면 끝..! (여기서는 돌을 몇개든 가져갈 수 있으므로 그런디 수는 항상 돌의 개수와 같다.) 

 

따라서, 코드는 아주 간단하게 나온다.

#include <bits/stdc++.h>

using namespace std;

int n,tmp;
int arr[101];
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        tmp=tmp^arr[i];
    }
    if(tmp) cout<<"koosaga";
    else cout<<"cubelover";
    return 0;
}