백준 28218번 격자 게임(2023 KOI 중등부 2번) C++(게임 이론)

문제 링크 : https://www.acmicpc.net/problem/28218

 

 

문제 풀이

 이 문제는 문제에 나온 격자칸에서 두 사람이 게임을 진행할 때 각 칸에 따라 선공이 이길지 후공이 이길지 판단하는 문제이다. 이런 유형의 문제는 게임이론에서 winning state와 losing state를 설정하는 것으로 풀 수 있다. 간단히 말하면 winning state는 받았을 때 이기는 게임의 상태를 의미하고 losing state는 받았을 때 지는 게임의 상태로서 재귀적으로 정의된다. 예를 들어서 상대가 마지막에 (N-1,M)칸으로 돌을 이동시켰다면,  (N,M)으로 칸을 이동시킬 수 있으므로 (N-1,M)은 winning state로 정의 된다.

winning state : 갈 수 있는 칸 중 losing state가 적어도 하나 존재하는 칸   (선공이 이기는 상태)
losing state : 갈 수 있는 칸이 모두 winning state인 칸  (후공이 이기는 상태)

 

 winning state를 true, losing state를 false로 지정하여 GameState라는 boolean 배열에 저장하자. 그럼 가장 먼저 (N,M)은 losing state임이 자명하기 떄문에 GameState[N][M] = false이다. 이제 간 칸에 대해 그 칸에서 갈 수 있는 칸 중 false(losing state)가 존재하는지 확인하여 false가 존재한다면 true, 아니라면 false로 저장하자. 이를 수식으로 써보면

시간복잡도는 모든 칸마다 최대 K+2번의 탐색을 거치는 것이기 때문에 O(MNK)이고, 테스트 케이스가 Q개 있으므로 전체로는 O(MNKQ)이다. M,N,Q ≤ 300이고 K < 300이므로 시간초과는 나지 않는다.

 

코드

#include <iostream>
using namespace std;

int N,M,K;
bool gameState[1000][1000],map[1000][1000];

bool State(int i, int j)
{
    if(map[i+1][j]&&!gameState[i+1][j]) return true;
    if(map[i][j+1]&&!gameState[i][j+1]) return true;
    for(int k=1;k<=K;k++)
    {
        if(map[i+k][j+k]&&!gameState[i+k][j+k]) return true;
    }
    return false;
}
int main() {
  cin>>N>>M>>K;
  for(int i=1;i<=N;i++)
  {
    for(int j=1;j<=M;j++)
    {
        char x;
        cin>>x;
        if(x=='.') map[i][j] = true;
    }
  }
  for(int i=N;i>=1;i--)
  {
    for(int j=M;j>=1;j--)
    {
        gameState[i][j] = State(i,j);
    }
  }
  int Q;
  cin>>Q;
  while(Q--)
  {
    int i,j;
    cin>>i>>j;
    if(gameState[i][j])
    {
        cout<<"First"<<"\n";
    }
    else
    {
        cout<<"Second"<<"\n";
    }
  }
}