백준 13034번: 다각형 게임 (스프라그-그런디 정리)

문제링크: 13034번: 다각형 게임 (acmicpc.net)

13034번: 다각형 게임

이 문제는 두명이 다각형 게임을 플레이하는데, 둘 다 모두 가장 이상적으로 행동한다고 했을 때 누가 이기는지 구하는 문제이다. 여기서 다각형 게임이란 N개의 꼭짓점으로 이루어진 이루어진 볼록 다각형에서 턴마다 번갈아가며 점 2개를 골라 선분을 긋는데, 여기서 선분은 이미 그은 선분과 교차하면, 점에서라도 교차하면 안된다. 그렇게 번갈아 선분을 그어나가다가 선분을 더이상 그을 수 없는 상태가 되면 해당 턴의 플레이어가 패배한다.

 

이 문제를 풀기 위해서는 스프라그-그런디 정리와 그런디 수에 대해 알아야 한다. 그런디 수에 대해 간략하게 설명하자면 현재 게임의 상태를 숫자로 치환한 것이다. 그런디 수 0을 게임의 마지막 상태 (승패가 정해진 상태)로 잡고, 게임의 여러 상태를 플레이어가 할 수 있는 행동의 경우에 따라 1, 2, 3... 이렇게 상태를 번호로 할당하는 식이다. 필승 전략 게임: 스프라그-그런디 정리 (casterian.net) 에서 자세한 설명을 보고 배울 수 있었다. 해당 상태의 그런디 수를 할당하는 법은 해당 상태에서 갈 수 있는 다음 상태의 그런디 수의 집합을 k 라 하면, k에 존재하지 않는 음이 아닌 가장 작은 정수를 할당한다. 이를 mex 라고도 한다.

 

어떤 상태 (t) 에서 행동을 한 후 다음 상태(t+1)의 그런디 수 집합이 {0}이라고 하자. 그러면 t의 그런디 수는 1이 될 것이다. 그리고 t+1상태는 상대 턴인데 그런디 수가 0이므로 상대가 패배하게 된다. 다르게 말하면 t상태는 무조건 승리할 수 있는 상태이다. 만약 어떤 상태 t의 그런디 수가 0보다 크다면, 상대 턴에 0을 만들 수 있으므로 무조건 승리할 수 있는 상태라고 생각할 수 있다. 여기서 한가지 의문이 들 수 있다. 그런디 수가 0보다 크면 모두 이길 수 있는 건데, 다 1로 표현하면 안되는 건가? 왜 2, 3, 4, 5 그런디 수들을 나누는 것일까? 0과 1로 표현하면 더 편한거 아닌가?

 

이는 N개의 게임을 동시에 진행 할 때 문제가 된다. 그런디 수가 1, 2인 게임 x, y를 동시에 플레이 하고, 플레이어 A, B가 있다고 하자. A는 할 수 있는 행동이 세가지 있다. x의 1 -> 0, y의 2 -> 1, 또는 y의 2 -> 0이다. A가 이기려면 어떤 행동을 해야 할까? 정답은 y의 2 -> 1이다. 이렇게 하면 x: 1, y: 1인 상태가 되고, B는 x나 y 둘중 하나를 무조건 0으로 만들어야 한다. 그러면 A는 나머지를 0으로 만들면, x: 0, y: 0 상태가 된 B는 무조건 패배하게 된다.

 

반면에 그런디 수가 2, 2인 게임이라고 하자. A는 할 수 있는 행동이 4가지 있지만, 한번 머릿속으로 계산해 보면 4개 중 어떤 행동을 해도 질 수 밖에 없다. 그러면 그런디 수 1, 2의 상태는, 특히 N개의 게임을 동시에 진행 할 때 확실히 다르다는 것을 알 수 있다. 

 

만약 N개의 게임을 같이 진행할 때의 그런디 수는 각 게임 상태의 N개의 그런디 수를 XOR 연산 해주면 된다고 한다. 여기서 XOR의 결과가 그런디 수가 1,2 에 따라 다르게 나와서 위와 같은 결과가 나온 것이다. 그러면 본격적으로 문제를 풀어보자.

 

이 문제에 대입하면 그런디 수 0은 더이상 선분을 그을 수 없는 상태이고, 해당 턴에 그런디 수가 0이라면 그 턴의 플레이어가 패배하게 된다. 그러면 이제 N개의 꼭지점이 있을때 그런디 수를 생각해보자.

N = 1 이면 점 1개이므로 선분을 그울수 없다. 그런디 수는 {0} 밖에 없다.

N = 2 이면 점 2개이므로 처음에 선분을 하나 그을 수 있다. 그런디 수는 {0, 1} 일 것이다.

N = 3 이면 점 3개이므로 처음에 그으면 하나가 남는다. 그런디 수는 {0, 1} 일 것이다.

N = 4 이면 점 4개이므로 처음에 중앙에 그으면 더이상 못긋고, 인접한 꼭짓점을 그으면 하나 더 그을 수 있다. 그러면 N=4의 초기 상태는 {0, 1}을 만들 수 있다. mex()를 하면 가장 초기의 그런디 수는 2가 될 것이다.

 

만약 점이 N개일 때 꼭짓점 2개를 정하면, 나머지 꼭지점들은 두개의 그룹으로 나뉘게 된다. 나뉘는 그룹의 꼭짓점 갯수 경우의 수는 (0, N-2), (1, N-3), (2, N-4) ..( (N-2)/2 , (N-2)/2 ) 가 될 것이다. 그룹이 나뉜다는 뜻은, 2개의 게임을 같이 진행한다고 봐도 무방하므로 XOR연산을 취하면 각 경우의 그런디 수를 구할 수 있다. 그렇게 각 경우의 그런디 수 집합을 구하고, mex()해주면 해당 상태의 그런디 수를 구할 수 있다.

import sys

N = int(sys.stdin.readline().rstrip())

grundys = [-1 for _ in range(1001)]

grundys[0] = 0
grundys[1] = 0
grundys[2] = 1

for i in range(3, 1001):
    cur = [0 for _ in range(1001)]
    for j in range(i//2 + 1):
        left = j
        right = (i - 2) - j
        cur[grundys[left]^grundys[right]] = 1
        
    for k in range(i):
        if cur[k] == 0:
            grundys[i] = k
            break
        
if grundys[N] == 0:
    print('2')
else:
    print('1')

이 문제는 N이 1000밖에 되지 않으므로 grundy[0], grundy[1], grundy[2]를 할당하고 간단하게 루프를 사용하여 bottom-up 방식으로 i가 3부터 1000까지, 각 N에서 모든 경우를 탐색하고 mex()하여 grundy[i] 를 구했다. 코드 구현은 쉽지만 그런디 수에 대한 이해가 어려웠다.