돌 게임
시간 제한1초메모리 제한1024 MB
1×N 판에 흑돌, 백돌, 빈 칸이 주어질 때 선공(흑)이 이기는지, 지는지, 무승부인지 판정합니다.
문제
크기가 인 게임판의 짝수 개의 칸에 흑돌과 백돌이 같은 개수로 번갈아 놓여 있다.
이 게임판으로 다음 규칙에 따라 게임을 한다.
- 선공과 후공이 한 턴씩 번갈아 진행한다. 선공은 흑, 후공은 백으로 둔다.
- 자신의 턴에 자신의 색 돌을 하나 골라 좌우로 원하는 만큼 움직일 수 있다. 돌을 움직이지 않고 넘길 수는 없다. 다른 돌을 뛰어넘거나 이미 돌이 있는 칸으로 움직이는 것은 불가능하다.
- 자신의 턴에 돌을 움직일 수 없는 플레이어가 진다.
두 플레이어가 최선의 전략으로 게임할 때 누가 이길지 구하라. 턴이 지나도 승부가 결정되지 않으면 무승부로 판정한다.
입력
첫 번째 줄에 게임판의 상태를 나타내는 문자열 가 주어진다.
는 B, W, .으로만 이루어져 있다. B는 흑돌, W는 백돌, .은 빈칸을 뜻한다. 흑돌과 백돌은 적어도 하나 이상 있음이 보장된다.
출력
첫 번째 줄에 선공이 이기면 Win, 지면 Lose를 출력한다. 턴이 지나도 승부가 결정되지 않으면 Draw를 출력한다.