돌 게임

시간 제한1초메모리 제한1024 MB

요약
한 줄에 번갈아 놓인 흑돌과 백돌을 각자 자기 색만 움직이는 게임에서, 최선의 전략으로 두었을 때 선공의 승패를 판정한다.
난이도

어려움10점 중 8점

유형
게임 이론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

크기가 1×N1 \times N인 게임판 위의 짝수 개의 칸에 흑돌과 백돌이 같은 개수로 번갈아서 배치되어 있다.

이 게임판을 이용해 게임을 하는데 규칙은 다음과 같다.

  • 선공과 후공이 한 턴씩 번갈아가면서 게임을 진행한다. 선공은 흑, 후공은 백으로 게임을 진행한다.
  • 두 플레이어는 자신의 턴에 자신의 색깔의 돌을 하나 선택하여 좌우로 원하는 만큼 움직일 수 있다. 돌을 움직이지 않을 수는 없으며, 다른 돌을 뛰어넘거나 이미 돌이 있는 칸으로 움직이는 것은 불가능하다.
  • 자신의 턴에 돌을 움직일 수 없는 플레이어가 게임에서 패배한다.

두 플레이어가 최선의 전략으로 게임을 할 때 누가 이길지 알아보자. 만약 1010010^{100} 턴이 지나도 승부가 결정되지 않으면 무승부로 판정한다.

입력

첫 번째 줄에 게임판의 상태를 나타내는 문자열 SS가 주어진다. (2≤∣S∣≤5,000)(2 \le \vert S\vert \le 5\\,000)

SS 는 B, W, .으로만 구성되어 있으며, B는 흑돌, W는 백돌, .은 빈칸을 의미한다. 흑돌과 백돌은 적어도 하나 이상 있음이 보장된다.

출력

첫 번째 줄에 선공이 이긴다면 Win, 선공이 진다면 Lose를 출력한다. 만약 1010010^{100} 턴이 지나도 승부가 결정되지 않으면 Draw를 출력한다.

예제2

  1. 예제 1

    입력
    W.BWB
    
    예상 출력
    Win
    
  2. 예제 2

    입력
    BWBW..
    
    예상 출력
    Lose