[BOJ] 백준 18939번 : 경비병 세우기 게임 (JAVA)

문제

Yuto 와 Platina가 보초 세우기 게임이라는 새로운 게임을 해보려고 한다. 이 게임은 N × M의 가로가 긴 격자판에서 진행된다.

 

게임은 항상 Yuto부터 시작하며, 둘은 번갈아 가면서 자신의 턴에 원하는 빈 위치에 경비병을 세운다.

 

이 게임에서 '안전상태'라는 것은 격자판 안에 완벽히 포함되는 어떤 K × K 크기의 정사각형에도 1명 이상의 경비병이 있는 상태를 의미한다.

 

안전상태가 된 순간 게임은 종료되고, 가장 최근 턴을 플레이 한 사람이 이기게 된다.

 

둘은 이 게임도 너무 재밌게 때문에 T판을 진행하려고 한다.

 

둘 다 최선의 플레이를 할 때, 모든 게임에 대해서 누가 이길지 예측해보자!

 

 

입력

첫째 줄에는 둘이 플레이 할 게임의 수 T가 주어진다.  

 

이후 T개의 줄에 각 게임의 게임판의 세로 길이와 가로길이, 그리고 정사각형의 크기를 나타내는 양의 정수 N, M, K가 순서대로 주어진다.

 

 

출력

각 케이스마다 한 줄에 걸쳐 이기게 될 플레이어의 이름 Yuto 혹은 Platina를 출력한다. 

 

 

풀이

필승 전략을 세우기 꽤나 까다로웠던 게임 이론 문제였습니다.

 

 

N * M 게임판 내에 속하는 모든 K * K 정사각형 지역을 안전 상태로 만드는 사람이 이기는 규칙이었습니다.

 

 

여기서, K * K 정사각형 지역을 편의상 안전 지역이라고 하겠습니다.

 

이때, N * M 게임판 내에서 경비병이 설치되지 않은 안전 지역들의 집합을 S라고 해 봅시다.

 

안전 지역은 게임판 안에 완벽히 들어가 있기만 하면 되기 때문에 여러 안전 지역이 서로 겹칠 수가 있습니다.

 

이제, S = {a₁, a₂, a₃, ... a_i, ...} 이라고 합시다.

 

이때,  a1 ∩ a2 ∩ a3 ∩ ...  ∩ ai ... ≠ ∅이라면, 특정 플레이어는 교집합에 해당하는 공간에 경비병을 설치함으로써 승리할 수 있습니다.

 

따라서, 우리는 첫 턴부터 바로 끝나는 경우는 제외하기 위해서  a₁ ∩ a₂ ∩ a₃ ∩ ...  ∩ a_i ...= ∅ 이라고 가정하겠습니다.

 

 

그렇다면, a_i와 a_j가 배반 사건인 순서쌍 (i, j)가 n (n >= 1) 개가 있을 것입니다.

 

시간이 지날수록 두 플레이어는 경비병을 놓기 때문에 n은 감소합니다.

 

이 때, 패배 조건은 현재 턴의 n = 0으로 만들어서 상대방에게 턴을 넘기는 경우이고, 언젠가 n = 1인 상황이 오기 때문에 두 플레이어 중에 한 명은 반드시 배반 사건인 지역을 하나 택해서 경비병을 놓아야 합니다.

 

그리고, 그 과정에서 먼저 경비병을 놓는 사람이 패배하게 될 것입니다.

 

 

이제, 우리는 선공이나 후공 중 누가 먼저 배반 사건 지역에 경비병을 놓는지 선택해야합니다.

 

먼저, 배반 사건을 제외한 나머지 영역의 개수는 N * M - 2 * K * K로 표현할 수 있습니다.

 

여기서 2 * K * K는 항상 짝수 개이므로 N * M이 홀수면 선공이 이기고, N * M이 짝수면 후공이 이기게 됩니다.

 

 

여기까지, 선공이 첫 턴에 바로 승리하지 않는다는 조건 하에, 선공과 후공의 필승 조건을 알 수 있었습니다.

 

마지막으로, 선공이 첫 턴에 바로 이기는 조건만 따지면 됩니다.

 

식은 단순합니다. max(N, M) < K * 2 를 만족한다면, 반드시 a1 ∩ a2 ∩ a3 ∩ ...  ∩ ai ... ≠ ∅ 조건을 성립할 것이기 때문에 선공이 이기게 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.