[Python] 백준 11717 - Wall Making Game

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

풀이

바로 이전에 스프라그 - 그런디 정리 소개글을 쓰고 왔다.

이 문제도 스그정리를 써서 풀 수 있다.

 

하나 깨달은 점은, 기존과 달리 2차원 게임에서, 각각의 '칸'에 그룬디 수를 정의할 수 있을 뿐만 아니라, 그냥 어떤 게임판의 일부분 그 자체가 그룬디 수 화 될 수 있음이다.

 

일단 한 가지 간단한 관찰을 하고 들어가보면, 벽과 x를 따로 구분하기 어려우니까 그냥 벽이 설치되는 것이 아니라 x가 설치되는 것이라고 생각해도 좋다.(사실 근데 크게 별로 상관은 없다.)

 

4차원 dp에다가 각 보드의 부분의 그룬디 수를 저장할 수 있다.

dp 형식은 

#dp[x1][y1][x2][y2]는 (x1, y1)부터 (x2, y2)까지의 보드의 Grundy Num.

 

으로 짰다.

 

시간복잡도 $O(H^{3}W^{3})$으로 모든 부분의 그룬디 수를 재귀적으로 계산할 수 있다.

 

어떤 (i, j)에서 벽을 설치하면 보드판이 독립적인 4개(이하)의 판으로 쪼개짐을 알 수 있다. 이 4개의 보드판을 nim sum해주면 (i,j)에서 벽을 설치했을 때의 그룬디 수가 된다.

 

어떤 보드판이 주어졌을 때, 모든 (i, j)에 대해서(다음 행동으로 가능한 경우의 수) 그룬디 수를 mex 해주면 최종적으로 현재 주어진 보드판 그 자체의 그룬디 수를 구할 수 있다.

 

H, W = map(int, input().split())
graph = []
for i in range(H):
    graph.append(list(input()))

#dp[x1][y1][x2][y2]는 (x1, y1)부터 (x2, y2)까지의 보드의 Grundy Num.
dp = [[[[None]*W for _ in range(H)] for _ in range(W)] for _ in range(H)]
for x in range(H):
    for y in range(W):
        if graph[x][y] == '.':
            dp[x][y][x][y] = 1
        else:
            dp[x][y][x][y] = 0

def sol(x1, y1, x2, y2):
    if x1 > x2 or y1 > y2:
        return 0

    if (not (0 <= x1 < H)) or (not (0 <= x2 < H)) or (not (0 <= y1 < W)) or (not (0 <= y2 < W)):
        return 0

    if dp[x1][y1][x2][y2] is not None:
        return dp[x1][y1][x2][y2]

    s = set()
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            if graph[i][j] == '.':
                s.add(sol(x1, y1, i-1, j-1) ^ sol(i+1, j+1, x2, y2) ^ sol(x1, j+1, i-1, y2) ^ sol(i+1, y1, x2, j-1))

    for g in range(401):
        if g not in s:
            dp[x1][y1][x2][y2] = g
            return g

if sol(0, 0, H-1, W-1) == 0:
    print('Second')
else:
    print('First')