[Python] 11717번 Wall Making Game

 

 

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

---

 

23/05/16

 

 

예전에 해결했던 스프라그 그런디 문제다. 재밌고 얻어갈 게 있는 문제라고 생각한다.

---

 

문제 접근 방식:

 

 

이미 마킹되어있는 칸은 고를 수 없고, 자신 턴에 빈 칸을 고르면 해당 빈 칸에서 4방향으로 뻗어나가 마킹된 칸을 만나거나 칸을 벗어날 때까지 모두 마킹을 한다.

 

문제에서 요구하는 건 이런 게임을 최적으로 플레이 할 때 누가 이기는 지의 여부를 따지는 것이다.

 

기존의 게임판이 있으면 한번 마킹할 때 4방향으로 갈라지므로, 4개의 작은 게임판으로 분할된다고 볼 수 있다.

 

그리고 그 작은 게임판들 각각에 대해서 그런디 수를 구한 뒤에, 그런디 수의 XOR값을 취해주면 해당 칸을 색칠할 때의 그런디수가  나오게 된다.

 

따라서 전체 보드에 대해 그 그런디 수들의 mex값을 취해주면 답이 된다.

 

결국은 보드를 어떻게 저장할 것인가? 가 핵심 부분이 된다고 생각을 하는데, 여러 방법이 있겠으나, 이 문제를 처음 풀 당시의 나는 하나의 보드를 하나의 튜플로 저장했다.

 

(문자열, r, c)와 같은 형태로 저장하고, 2차원의 보드를 1차원으로 핀 문자열을 튜플로 저장했다.

 

그리고 그걸 딕셔너리에 넣어서 저장하면서 구현을 진행했던 기억이 있다.

 

분할된 게임판을 구할 때에는 r과 c를 통해 구현했다. 자세한 내용은 코드를 참고하자.

---

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

# 11717번 Wall Making Game
# DP, 게임 이론, 스프라그-그런디 정리, 분할 정복
import sys
input = sys.stdin.readline

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

H, W = map(int, input().rstrip().split())
game = ''.join(input().rstrip() for i in range(H))
DP = dict()
DP[('X', 1, 1)] = 0
DP[('.', 1, 1)] = 1
DP[('', 0, 0)] = 0
def find_nim(game, H, W):
    if game in DP:
        return DP[game]
    S = set()
    for i in range(H*W):
        if game[i] == '.':
            
            row, col = i//W, i%W
            total = 0
            
            game1 = ''
            if row > 0 and col > 0:
                j = 0
                while j < row*W:
                    game1 += game[j]
                    j += 1
                    if j % W == col:
                        j += (W-col)
                if (game1, row, col) not in DP:
                    find_nim(game1, row, col)
                total ^= DP[(game1, row, col)]
            
            game2 = ''
            if row > 0 and W-col-1 > 0:
                j = col+1
                while j < row*W:
                    game2 += game[j]
                    j += 1
                    if j % W == 0:
                        j += (col+1)
                if (game2, row, W-col-1) not in DP:
                    find_nim(game2, row, W-col-1)
                total ^= DP[(game2, row, W-col-1)]

            game3 = ''
            if H-row-1 > 0 and col > 0:
                j = (row+1)*W
                while j < H*W:
                    game3 += game[j]
                    j += 1
                    if j % W == col:
                        j += (W-col)
                if (game3, H - row - 1, col) not in DP:
                    find_nim(game3, H-row-1, col)
                total ^= DP[(game3, H-row-1, col)]

            game4 = ''
            if H-row-1 > 0 and W-col-1 > 0:
                j = (row+1)*W + col + 1
                while j < H*W:
                    game4 += game[j]
                    j += 1
                    if j % W == 0:
                        j += (col+1)
                if (game4, H-row-1, W-col-1) not in DP:
                    find_nim(game4, H-row-1, W-col-1)
                total ^= DP[(game4, H-row-1, W-col-1)]

            S.add(total)
    DP[(game, H, W)] = mex(S)
    return DP[(game, H, W)]

winlose = find_nim(game, H, W)
print('First' if winlose else 'Second')