[Python] 8845번 Gra

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

8845번: Gra

---

 

23/05/31

 

 

스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다.

 

비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다.

 

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

10363번: Circle and Marble

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

27306번: DAGame

---

 

문제 접근 방식:

 

 

문제가 폴란드어로 작성되어있기 때문에 나의 의역을 덧붙여본다.

원제: Gra
의역 제목: 훈이와 짱구의 게임

문제:
훈이는 짱구와 보드 게임 하는 것을 좋아합니다.
보드 게임에 사용되는 판은 '칸'들과, 그 '칸'들을 잇는 단방향 간선들로 이루어져 있습니다.
훈이가 가지고 있는 모든 보드 게임들은 공통적으로 '칸'들을 두 번 이상 지날 수 없다는 특징을 가지고 있습니다.

불행하게도, 훈이와 짱구는 훈이가 가지고 있는 모든 게임들을 매우 잘 알고 있어서 더 이상 재밌게 즐길 수 없습니다. 그래서 훈이는 보드 게임을 새롭게 즐길 아이디어를 하나 고안해 냈습니다.

훈이의 아이디어는 다음과 같습니다.
훈이는 자신의 보드게임 컬렉션 중 아무거나 두 개를 뽑아서 '동시에' 게임을 진행합니다.
그리고 각각의 보드게임 마다, 말을 하나씩 놓습니다.
그리고 나서 훈이와 짱구가 서로 턴을 주고받으며 말을 움직입니다.
말은 '칸'에서 다른 '칸'으로 움직이는데, '칸'을 잇는 단방향 간선을 통해서만 움직일 수 있습니다.
게임은 훈이가 항상 먼저 시작합니다.
만약 두 게임 모두에서 말을 움직일 수 없다면, 해당 플레이어는 집니다.

훈이는 말이 놓이는 초기 상황이 주어지고, 이 상황에서 서로가 항상 최적의 플레이를 한다고 가정하면, 누가 이길지 궁금해합니다. 훈이에게 누가 이길지 알려주세요!

입력:
프로그램 입력은 두 개의 게임 판에 대한 설명으로 시작합니다.
각 게임판의 정보는 '칸'의 개수 $N$과 '칸'을 잇는 간선의 개수 $M$ $(1\leq N, M\leq100000)$으로 시작합니다.
이후 $M$개의 줄에 $A$번 칸에서 $B$번 칸으로 이어지는 간선의 정보가 $a$ $b$의 형식으로 들어옵니다.
각 칸들은 숫자로 $1$번부터 $N$번까지 매겨져 있습니다.

게임판에 대한 입력이 끝난 후, 훈이가 궁금해하는 초기 상황이 몇 개나 되는지에 대한 숫자 $Q$가 들어옵니다. $(1 \leq Q \leq 100000)$

이후, $Q$개의 줄마다 $X$ $Y$의 형식으로 말이 놓이는 초기 상황이 들어옵니다.
이는 첫 번째 게임의 말이 $X$번째 칸에, 두 번째 게임의 말이 $Y$번째 칸에 있음을 의미합니다.


출력:
훈이가 궁금해하는 초기 상황이 $X$ $Y$의 형식으로 주어질 때마다, 훈이가 이긴다면 'W'를, 짱구가 이긴다면 'P'를 줄을 바꿔서 출력해 주세요.

 

먼저, 문제 해결을 위해 알아야 할 지식이 있다.

 

스프라그-그런디 정리가 적용될 수 있는 게임들은 DAG로 모델링 될 수 있다는 사실이다.

 

실제로, 이 문제에서 나오는 게임은 DAG위에서 말을 움직이다가 더 이상 갈 수 없을 때 종료되는 게임이다.

 

 

 

그런디 수를 구하는 방법을 한번 곰곰이 생각해 보자.

 

어떤 특정 게임판에 대한 그런디 수는, 그 게임판에서 다른 게임판들로 상황을 변화시킬 수 있을 때, 그 다른 게임판들의 그런디 수의 $mex$값으로 재귀적으로 정의가 된다.

 

만약 한 게임판에서 더 이상 다른 게임판으로 상황을 변화시킬 수 없다면, 즉, 다시 말하자면, 내가 할 수 있는 행동이 더 이상 존재하지 않는다면, 그 게임판에 대한 그런디 수는 $0$이 된다.

 

 

 

이 사실을 안다면, DAG위에 말이 하나가 놓여 있고, 방문했던 칸은 더 이상 방문하지 못하는 게임을 그런디 수로 바꿀 수 있다는 사실을 알 수 있다.

 

우리는 보드 게임 2개를 동시에 진행한다는 사실을 알고 있으므로, 그냥 초기에 말이 어떻게 놓여 있는지에 대한 정보가 주어진다면, 각각의 보드 게임에 대해 그런디 수를 구하고 $XOR$을 하면 된다는 사실을 알고 있다.

 

그렇다면, 보드 게임 하나에 대해서 그 그런디 수를 어떻게 구할 것인가? 가 문제의 핵심 요소가 될 것이다.

 

 

 

위에서 이야기했듯, 게임판 위에 말이 놓인 초기 상황이 주어진다면, 그 상황에 대한 그런디 수를 구하려고 한다면 그 게임판에서 다른 게임판으로 갈 수 있을 때 다른 게임판들의 그런디 수의 $mex$값이 그 상황에 대한 그런디 수가 된다.

 

예를 들어, 초기 상황이 $1$번 노드에 말이 놓여 있는 상황이라고 해보고, $1$번 노드에는 $2$번과 $3$번이 연결돼있다고 해보자.

 

이 상황에 대한 그런디 수를 구하고자 한다면, 말은 $1$번 노드에서 $2$번 노드 또는 $3$번 노드로 이동할 수 있으므로, 즉, 말이 $2$번 노드에 놓여있는 상황이나 $3$번 노드에 놓여있는 상황으로 초기 상황을 바꿀 수 있으므로, 말이 $2$번 노드에 놓여있을 때의 그런디 수와 $3$번 노드에 놓여있을 때의 그런디 수의 $mex$값으로 구해질 것이다.

 

그러면 $2$번 노드에 말이 놓여있는 상황에 대한 그런디 수는 어떻게 구할까?

 

이것 또한 마찬가지로 재귀적으로 구하면 된다.

 

그러다가 더 이상 말이 움직일 수 없을 때, 그런디 수를 $0$이라고 하면 된다.

 

 

 

이는 DFS로도 구현할 수 있고, 위상 정렬을 통해 구현할 수도 있다.

 

또 어떻게 보면, 점화식이 조금 독특한 탑다운 DP라고 생각할 수 있다.

 

어쨌든 그렇게 각각의 보드게임에 대해서 그런디 수들을 구해서 각 초기 상황이 주어지는 쿼리마다 $XOR$해주면 된다.

 

 

 

이와 비슷한 문제, DAGame에 대한 해설도 있으니, 더 자세히 알고 싶다면 아래 글을 참조해도 될 것이다.

 

2023.05.04 - [백준 문제 풀이] - [Python] 27306번 DAGame

[Python] 27306번 DAGame

 

---

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

# 8845번 Gra
# 게임 이론, 스프라그-그런디 정리, 그래프 이론, 그래프 탐색, DFS, DP
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def mex(S):
    S = sorted(S)
    for i in range(len(S)):
        if i != S[i]:
            return i
    return len(S)

N1, M1 = map(int, input().rstrip().split())
graph_1 = [[] for _ in range(N1)]
grundy_1 = [-1 for _ in range(N1)]
for _ in range(M1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    graph_1[a].append(b)
def find_grundy_1(node):
    if grundy_1[node] != -1:
        return grundy_1[node]
    S = set()
    for near_node in graph_1[node]:
        if grundy_1[near_node] == -1:
            find_grundy_1(near_node)
        S.add(grundy_1[near_node])
    grundy_1[node] = mex(S)
    return grundy_1[node]

N2, M2 = map(int, input().rstrip().split())
graph_2 = [[] for _ in range(N2)]
grundy_2 = [-1 for _ in range(N2)]
for _ in range(M2):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    graph_2[a].append(b)
def find_grundy_2(node):
    if grundy_2[node] != -1:
        return grundy_2[node]
    S = set()
    for near_node in graph_2[node]:
        if grundy_2[near_node] == -1:
            find_grundy_2(near_node)
        S.add(grundy_2[near_node])
    grundy_2[node] = mex(S)
    return grundy_2[node]

Q = int(input())
for _ in range(Q):
    X, Y = map(lambda x: int(x)-1, input().rstrip().split())
    win = find_grundy_1(X)^find_grundy_2(Y)
    print('W' if win else 'P')