| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
「Move or Block!」 게임은 N칸의 일자형 게임보드에서 할 수 있는 2인용 보드게임이다. 게임보드의 각 칸은 비어 있거나 벽이 세워져 있으며, 비어 있는 칸 중 하나에 두 플레이어가 움직일 수 있는 하나의 말을 올려두고 게임을 시작한다. 게임은 두 명의 플레이어가 턴을 번갈아 가면서 진행한다.
각 플레이어는 자신의 턴이 되었을 때 말의 인접한 칸에 모두 벽이 세워져 있으면 패배한다. 아니라면 아래 두 가지 행동 중 하나를 선택하여 한 번 플레이하고 턴을 넘긴다.
- 말을 비어 있는 인접한 칸 중 하나로 움직인다.
- 비어 있는 칸을 하나 골라 벽을 세운다.
민규와 윤수가 「Move or Block!」 게임을 하려 한다. 주어진 게임보드에서 두 플레이어 모두 최적의 방법으로 게임을 진행했을 때 이기는 플레이어를 출력한다. 게임은 민규가 먼저 시작한다.
입력
첫 번째 줄에 게임보드의 크기 N이 주어진다.
두 번째 줄에 초기 게임보드의 상태로 길이가 N인 문자열이 주어진다. 게임보드는 .(온점),X,O세 문자로만 구성되어 있고, 각각 비어 있는 칸, 벽이 세워져 있는 칸, 말을 올려둔 칸을 의미한다.
출력
민규가 이기는 경우에는 mingyu, 윤수가 이기는 경우에는 yunsu, 만약 게임이 영원히 끝나지 않는다면 draw를 출력한다.
제한
- 2 ≤ N ≤ 1,000,000
- 입력으로 주어지는 N은 정수이다.
- 말은 게임보드에 정확히 하나만 존재한다.
- 말의 인접한 칸에 모두 벽이 세워져 있는 경우는 입력으로 주어지지 않는다.
풀이
게임의 승리 조건을 파악하는 문제다.
먼저 말이 놓여있는 구간을 봤을 때 왼쪽 빈칸의 수를 l, 오른쪽 빈칸의 수를 r, 그 바깥의 모든 빈칸의 수를 c라고 하자.
게임에서 반드시 이기거나 지는 조건들을 살펴보면 이렇다.
(1) 말의 한 쪽이 막힌 경우
칸이 이상한데 말의 한 쪽이 막힌 경우는 민규가 나머지 한 쪽을 막아버리면 바로 승리할 수 있다. 따라서 l = 0 이거나 r = 0인 경우, 민규의 승리다. 양쪽이 모두 막힌 경우는 입력으로 주어지지 않으니 한 턴에 윤수가 승리하는 경우는 없다.
(2) 3 block case
이름이 좀 거창한데 뭐라 부를 마땅한 게 없어서 '3칸의 경우'로 부르겠다.
이 경우는 l 과 r 모두 1인 경우다. 이 상태로 턴을 넘겨받은 사람은 무슨 수를 두어도 반드시 패한다. 따라서 시작 상태에 l = 1이고 r = 1이라면 3block case를 받은 민규는 패배한다. 하지만 여기에는 함정이 하나 있다. 바로 c의 존재다. c가 있다면 3 block case로 턴을 받은 상대는 c 중의 한 칸에 벽을 세워서 턴을 넘겨버린다. 그럼 3 block case에서 c가 홀수라면 윤수가 패배하고 짝수라면 민규가 그대로 패배한다.
왜 턴 넘김이라는 방법을 택해야 하냐면 3 block case 안에서 어떤 수를 두게 되면 반드시 다음 턴에 패배하기 때문이다.
잘 생각해보면 양쪽이 다 열린 말의 한 쪽을 막는 건 자충수다. 다음 턴에 나머지 한 쪽이 막힌채 나의 턴이 되기 때문이다. 승리 조건을 만들기 쉬운 방법은 3block case를 만드는 것이다.
(3) near 3 block case
이 경우에는 3 block case를 만들어 상대에게 턴을 넘길 수 있다. 이 때, 남은 c가 문제가 되는데 한 쪽의 남은 간격을 1로 만들기 때문에 나머지 칸을 바깥 구간으로 버리게 된다. 그러니까 위 그림의 경우는 r-2만큼의 칸을 c로 넘겨버리는 것이고, c+r-2가 홀수라면 이 가불기는 나에게 돌아와버린다. 따라서 이 조건을 따져야 한다.
만약 l이 1이라면 r+c(a-2가 짝수라면 a도 짝수임)가 짝수인 경우와 홀수인 경우로 나눌 수 있는데, 여기서 홀수인 경우는 자충수다. 따라서 r+c가 짝수인 경우만 이 방법을 사용하고, 그 경우에 민규가 승리한다. 홀수인 경우에는 이 방법을 사용하지 않고 다음과 같은 규칙을 따라 수를 둔다.
(4) 무한반복
3 block case를 만들면 남는 칸이 홀수인 경우, 자충수를 피하면 할 수 있는 것은 둘 중 하나다. 말을 벽 반대로 옮기거나, c 중 하나에 벽을 세우는 것이다.
그런데 서로 패배 조건의 3 block case를 피하려면 여기서 말을 계속 왔다갔다 하는 수밖에 없다. 게다가 이외의 모든 경우에 대해서 서로가 승리조건을 만들다보면 c는 어찌되었든 소진되고 l과 r은 점점 줄어 민규의 차례가 되었을 때 다음 상황이 온다.
여기서부터 민규와 윤수는 패배조건에서 피하기 위해 말 옮기기 밖에 할 수 없다. 따라서 위에서 다룬 조건 이외에는 모두 비기는 경우다.
증명이 너무 어렵다...
정답 코드
code제출번호 74738905가 이 문제 최고의 해법인 것 같다.
