[Python] 28218번 격자 게임

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

---

 

24/05/24

 

 

간단한 게임 DP 문제이다. 최근 게임 이론 문제들을 많이 풀어보고 있는데, 꽤나 재미있다.

---

 

문제 접근 방식:

 

 

접근 방식은 나이브한 게임 DP이다.

 

골드 난이도에서 진행되는 게임 DP는 스프라그-그런디 정리가 섞이는 경우가 없기 때문에, 그냥 누가 이기는지 지는지에 대한 여부만 DP배열에 저장해주면 된다.(즉, 님버를 굳이 저장할 필요가 없다.)

 

선공이 지는 포지션을 0으로 저장하고, 선공이 이기는 포지션을 1로 저장하자.

 

내가 어떤 행동을 통해 말을 움직이면, 움직여진 게임 판 그대로 상대방이 처음부터 시작하는 것과 같다.

 

즉, 내가 어떤 행동을 통해 말을 움직여서 나의 턴을 끝내면, 그 상태 그대로 상대방이 선공으로 시작하는 것과 동일한 결과가 된다.

 

그래서, 내가 어떤 행동을 하는데, 그 행동을 통해 선공이 지는 포지션으로 갈 수 있다면, 내가 있는 곳은 선공이 이기는 포지션이 된다.

 

즉, 내가 행동을 해서 상대방에게 턴을 넘겨주는 것은 선/후공을 뒤바꾸는 행위와 같기 때문에, 내가 어떤 행동을 해서 선공이 지는 포지션으로 만들고, 상대방에게 선공을 하도록 넘겨준다면? 그 말은 내가 이긴다는 뜻이 된다.

 

따라서 내가 있는 곳은 선공이 이기는 포지션이 된다.

 

모든 게임 DP가 이런 식으로 동작하는데, 격자게임은 그게 2차원일 뿐이다.

 

유의할 점은 시간 제한이 조금 빡빡하다는 점.

 

처음에는 님버를 구하는게 편해서 님버를 구하려고 했다가 시간 초과를 받았고, 이후 0과 1로만 판단하도록 바꿨으며, 적절한 break문으로 반복문을 끊어줌으로써 빠르게 판단하도록 했다. 

---

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

# 28218번 격자 게임
# 게임 이론
'''
접근 방법:
게임 DP
'''
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]
DP = [[-1 for _ in range(M)] for _ in range(N)]
DP[N-1][M-1] = 0
for i in range(N-1, -1, -1):
    for j in range(M-1, -1, -1):
        if board[i][j] == '#': continue
        if i == N-1 and j == M-1: continue
        flag = True
        if 0 <= i+1 < N and board[i+1][j] == '.' and DP[i+1][j] == 0:
            flag = False
        if flag and 0 <= j+1 < M and board[i][j+1] == '.' and DP[i][j+1] == 0:
            flag = False
        if flag:
            for k in range(1, K+1):
                if 0 <= i+k <= N-1 and 0 <= j+k <= M-1 and board[i+k][j+k] == '.' and DP[i+k][j+k] == 0:
                    flag = False
                    break
        if flag:
            DP[i][j] = 0
        else:
            DP[i][j] = 1
Q = int(input())
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1; y -= 1;
    if DP[x][y]:
        print('First')
    else:
        print('Second')