[Python] 13034번 다각형 게임 / 16187번 Game on Plane

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

13034번: 다각형 게임

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

16187번: Game on Plane

---

 

22/10/09

 

 

이 두 문제는 문제의 내용이 약간 다르긴 하지만, 모두 같은 풀이 방법을 공유하기에 같이 적는다.

 

이 글은 게임 이론에 대한 내용, 특히, 스프라그-그런디 정리에 대한 내용을 알고 있다는 전제 하에서 해설이 쓰여있으므로 이 글을 보거나 이 문제의 해설을 이해하고자 한다면 스프라그-그런디 정리에 관한 선행지식이 필요하다.

---

 

문제 접근 방식:

 

 

먼저, 다각형 게임을 기준으로 설명하겠다.

 

다각형 게임의 규칙은 다음과 같다.

 

N개의 꼭짓점으로 이루어진 볼록 다각형이 있다.

각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다).

이때, 이미 그려져 있는 선분과 교차하면 안 된다 (선분의 끝 점에서 겹치는 것도 교차하는 것이다).

더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.

 

규칙의 마지막 부분을 보면, 더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다고 했으므로, 이 게임은 자기 차례에 할 수 있는 행동이 하나도 없으면 패배하는 노멀 게임(normal game)에 해당한다.

 

또한, 성관이와 홍준이가 그은 선분들은 모두에게 공유되고 공개가 되므로, 모든 참가자들이 게임에 대한 정보를 공유하는 완전 정보 게임(perfect information game)에 해당한다.

 

또한, "선분을 긋는다"는 행위는 바둑처럼 흰 돌과 검은 돌로 구분되는 것이 아닌, 즉, 누가 하든지 간에 구분이 되지 않는 행동이므로, 이 게임은 참가자가 할 수 있는 행동들의 집합이 전적으로 게임판의 상황에 따라 달린 공정 게임(impartial game)이라고 할 수 있다.

 

때문에 이 게임은 스프라그-그런디 정리의 조건을 만족하므로, 각 게임판의 상황을 하나의 그런디 수로 치환할 수 있다.

 

 

먼저, Base Case(점 0개, 점 1개, 점 2개)를 따져주자.

 

만약 점이 0개인 경우, 우리는 선분을 그을 수 없으므로 이때의 그런디 넘버는 0이 된다.

 

만약 점이 1개인 경우에도, 우리는 선분을 그을 수 없으므로 이때의 그런디 넘버는 0이 된다.

 

점이 2개인 경우는, 선분을 한 번 그으면 점이 0개인 경우로 갈 수 있으므로 이때의 그런디 넘버는 1이 된다.

 

 

기본 케이스를 이용하여 그 이상의 경우를 구해보자.

 

임의로 우리가 선분을 그으면, 그것을 기준으로 왼쪽과 오른쪽으로 다각형이 분할됨을 알 수 있다.

 

분할된 다각형 또한 볼록 다각형임을 알고 있으므로, 선분을 긋는 행위는 게임판의 상황을 둘로 나누는 것과 동일하다는 것을 알 수 있다.

 

스프라그-그런디 정리에 따르면, 두 개 이상의 게임판이 놓여있는 게임판 그룹이 있을 때, 그 그룹의 모든 게임판의 그런디 넘버에 XOR을 취해주면 그 그룹의 그런디 넘버를 구할 수 있다.

 

게임판의 상황을 둘로 나누는 것은 게임판 그룹을 만드는 것이고, 우리는 위의 성질을 이용하여 그 그룹의 그런디 넘버를 구할 수 있으므로, 점이 3, 4, 5,... 그 이상의 경우에서도 그런디 넘버를 구할 수 있을 것이다.

 

 

예를 들어 점 3개, 점 4개, 점 5개인 경우를 보자. 

 

점이 3개인 경우는, 선분을 한 번 그으면 점이 1개인 경우로 갈 수 있으므로 이때의 그런디 넘버는 1이 된다.

 

게임을 분할 한다는 측면에서 보자면, 점이 3개일 때에는 점이 0개인 경우와 점이 1개인 경우로 분할하는 것과 동일하므로, (이미 다각형을 분할할 때 사용했던 점 2개는 사용할 수 없으므로) 그런디 넘버를 구한다면 mex(grundy(0)^grundy(1)) = mex(0^0) = 1이다.

 

점이 4개인 경우, 우리는 선분을 한 번 그으면 점이 0개인 경우와 2개인 경우로 분할됨을 알 수 있다. 또한, 점이 1개인 경우와 점이 1개인 경우로 분할됨을 알 수 있다.

 

따라서 mex(grundy(0)^grundy(2), grundy(1)^grundy(1)) = mex(0^1, 0^0) = 2가 점 4개인 경우의 그런디 넘버가 된다.

 

점이 5개인 경우, 우리는 선분을 한 번 그으면 0개와 3개, 1개와 2개, 2개와 1개로 분할 됨을 알 수 있다.

 

이 경우 또한, 분할된 게임 2개의 그런디 넘버에 XOR연산을 취해주고, 그 상황 3개에 mex함수를 적용시켜 mex(0^1, 0^1, 1^0) = 0이라는 그런디 넘버를 얻어낼 수 있다.

 

이를 그대로 코드로 구현하면 끝이다.

 

 

Game on Plane의 문제 설명은 다각형 게임과는 약간 다르다.

 

Game on Plane의 문제 설명은 다음과 같다.

N개의 꼭짓점으로 이루어진 볼록 다각형이 있다.

각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다).

이때, 이미 그려져 있는 선분과 교차하면 안 된다. (선분의 끝 점에서 겹치는 것은 가능이다)

더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.
또한, 선분을 그었을 때, 다각형을 만들었다면 다각형을 만든 사람이 승리한다.

선분의 끝 점 부분이 조금 다르게 설명이 되어있는데, 이것 또한 사실상 다각형 게임의 조건과 똑같은 조건이다.

 

다각형 게임에서는 선분의 끝 점에서 겹치면 안된다고 되어있었는데, 여기에서는 선분의 끝 점에서 겹쳐도 되는 대신에, 선분을 그었을 때 다각형이 만들어진다면 승리하는 조건으로 되어있다.

 

근데 사실상 저 조건은 선분의 끝 점에서 겹치면 안된다는 조건과 같다.

 

왜냐하면, 만약 내 차례 때 선분을 긋는데 선분의 끝 점에 겹치게 선분을 그었다고 해보자.

 

그러면 상대방 차례때에는 내가 방금 그었던 선분의 끝점과 이미 선분이 있었던 점을 이어서 다각형을 만들 수 있기 때문에 무조건 내가 지기 때문이다.

 

때문에 이 부분만 다르게 보이지만, 사실상 같은 조건이기 때문에 같은 풀이를 동일하게 적용하여 풀 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 13034번 다각형 게임
# 게임 이론, 스프라그-그런디 정리
'''
접근 방법:
최적의 방법으로 게임을 하므로 항상 겹치지 않게 선분을 그을 것이다.
그러면 선분을 긋는다면, 이 행위는 게임을 나누는 행위와 같다.
그런디 넘버
점이 0개 -> 0
점이 1개 -> 0
점이 2개 -> 1
점이 3개 -> mex(g(0)^g(1)) = 1
점이 4개 -> mex(g(0)^g(2), g(1)^g(1),) = 2
점이 5개 -> mex(g(0)^g(3), g(1)^g(2), g(2)^g(1), ) = 0
점이 6개 -> mex(g(0)^g(4), g(1)^g(3), g(2)^g(2))
'''
N = int(input())
def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)
grundy = [0, 0, 1]
for i in range(3, N+1):
    S = set()
    for j in range(i-1):
        S.add(grundy[j]^grundy[i-2-j])
    grundy.append(mex(S))
print(1 if grundy[N] else 2)

# 16187번 Game on Plane
# 게임 이론, 스프라그-그런디 정리
'''
접근 방법:
최적의 방법으로 게임을 하므로 항상 겹치지 않게 선분을 그을 것이다.
그러면 선분을 긋는다면, 이 행위는 게임을 나누는 행위와 같다.
그런디 넘버
점이 0개 -> 0
점이 1개 -> 0
점이 2개 -> 1
점이 3개 -> mex(g(0)^g(1)) = 1
점이 4개 -> mex(g(0)^g(2), g(1)^g(1),) = 2
점이 5개 -> mex(g(0)^g(3), g(1)^g(2), g(2)^g(1), ) = 0
점이 6개 -> mex(g(0)^g(4), g(1)^g(3), g(2)^g(2))
'''
def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)
grundy = [0, 0, 1]
for i in range(3, 5000+1):
    S = set()
    for j in range(i-1):
        S.add(grundy[j]^grundy[i-2-j])
    grundy.append(mex(S))

for _ in range(int(input())):
    N = int(input())
    print('First' if grundy[N] else 'Second')