문제 링크 : 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";
}
}
}
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 14500번 테트로미노 C++ (1) | 2024.06.08 |
---|---|
백준 28325번 호숫가의 개미굴 C++ (0) | 2024.05.25 |
백준 1005번 ACM Craft C++ (0) | 2024.04.21 |
백준 16891번 탄성충돌 C++ (물리) (0) | 2024.03.24 |
백준 30928번 Yokohama Phenomena C++ (1) | 2024.03.23 |