시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 1024 MB | 17 | 7 | 7 | 63.636% |
《체스》는 $8 \times 8$ 격자 모양의 체스판 위에서 각자의 기물을 이용해 상대를 체크메이트시키는 것이 목적인 2인 제로섬 유한 확정 완전 정보 게임입니다. 각 플레이어는 흰색 측과 검은색 측이 되어 자기 색의 말을 각각 번갈아가면서 한 번씩 움직이게 되고, 상대의 킹을 체크메이트시키면 이기는 게임입니다.
기물의 움직임에 대한 공통적인 규칙은 다음과 같습니다.
1, 4번 규칙에는 캐슬링과 앙 파상이라는 예외가 있지만, 이 문제에서는 등장하지 않습니다.
체스의 기물은 총 $6$종류가 있으며, 움직이는 법은 같습니다.
이 게임에서 가장 중요한 개념 중 하나는 체크 상태입니다. 어떤 색의 킹이 체크 상태에 있다는 것은 다른 색의 기물이 한 번의 움직임으로 킹이 있는 위치로 갈 수 있다는 것을 말합니다. 기물의 움직임이 끝난 후, 자신의 킹이 체크 상태이면 안 됩니다. 즉, 자신의 킹이 체크 상태에 놓이는 것을 피해야 합니다.
상대의 킹이 체크 상태이고 상대가 다음 턴에 어떤 수를 두더라도 체크 상태를 피할 수 없는 경우 상대의 킹이 체크메이트되었다고 하며, 이 경우 게임에서 승리합니다. 단, 상대의 킹이 체크 상태가 아니면서 상대가 다음 턴에 어떤 수를 두더라도 체크 상태를 피할 수 없는 경우는 스테일메이트가 되고, 게임이 비기게 됩니다.
체크메이트와 스테일메이트 이외에 게임이 종료되는 경우는 다음과 같으며, 이 경우들로 인해 게임이 종료되는 경우에는 무승부로 처리됩니다.
체스는 원래 각자 $16$개의 말을 가지고 시작하지만, 체스에서는 엔드게임이라고 불리는 단계가 매우 중요합니다. 이 단계는 기물이 별로 남지 않았을 때를 의미하고, 치밀한 수 계산을 해야 승리할 수 있습니다. 지금 상황은 체스판 위에 흰색 킹과 폰이 각각 하나씩 있고, 검은색 기물은 킹만 하나 있는 상태입니다. 양측이 최선을 다할 때, 흰색 측이 승리할 수 있을지 혹은 무승부가 될지, 승리한다면 몇 수 이내로 승리할 수 있을지 계산하는 프로그램을 만들어봅시다. 최선을 다한다는 것은 어떤 측이 이길 수 있다면 최대한 적은 수로 이기려고 하며, 이길 수 없지만 비길 수 있다면 비기려고 하며, 질 수밖에 없는 경우는 최대한 많은 수를 두려고 함을 의미합니다.
입력은 $T$ 개의 테스트 케이스로 이루어집니다. 입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다. $(1 \le T \le 200\,000)$
각 테스트 케이스는 $8$개의 줄로 이루어져있습니다. 테스트 케이스의 첫 $8$개의 각 줄에는 길이가 $8$인 문자열이 주어집니다. $i$번째 줄의 $j$번째 문자는 위에서 $i$번째, 왼쪽에서 $j$번째 칸에 대한 정보를 나타냅니다.
.
: 현재 칸이 비어있다는 것을 나타냅니다.K
: 현재 칸에 흰색 킹이 있다는 것을 나타냅니다,P
: 현재 칸에 흰색 폰이 있다는 것을 나타냅니다.k
: 현재 칸에 검은색 킹이 있다는 것을 의미합니다.이후 마지막 줄에는 W
혹은 B
문자가 주어집니다. W
문자는 현재 차례가 흰색 차례, B
문자는 현재 차례가 검은색 차례라는 것을 의미합니다.
한 테스트 케이스에는 K
, P
, k
문자가 정확히 하나씩 등장합니다. 주어지는 체스판은 게임이 진행 중이며 올바른 상태입니다. 이는, 폰이 가장 위 혹은 아래 행에 있지 않으며, 현재 차례의 상대편 킹이 체크 상태가 아니고 현재 차례에 (본인의 킹을 체크시키지 않는) 가능한 움직임이 존재한다는 것을 의미합니다.
각 테스트 케이스마다 한 줄에 하나씩 정수 하나를 출력합니다. 서로가 최적으로 플레이했을 때, 검은색 킹을 체크메이트시킬 수 있다면, 필요한 흰색 기물 이동 횟수를 출력합니다. 체크메이트시킬 수 없고 무승부로 끝난다면 $0$을 출력합니다.
2 ...k.... ...P.... ....K... ........ ........ ........ ........ ........ W ...k.... ...P.... ....K... ........ ........ ........ ........ ........ B
0 8
Contest > BOJ User Contest > 보드게임컵 > 보드게임컵 I번