【백준】- 16341. Horsemeet

문제

https://www.acmicpc.net/problem/16341

16341번: Horsemeet

문제를 간단히 요약하면...

• 두 나이트가 $8 \times 8$ 내의 체스판에서 정해진 위치에 놓여 있고, 백부터 시작해 차례대로 한 번씩 이동합니다. 상대방의 말의 위치로 먼저 이동하는 쪽이 승리합니다.
• 각 나이트가 이동 가능한 모든 위치에 대해 새로운 위치를 고르는 확률은 동일합니다.
• 백과 흑 중, 승리할 확률이 더 높은 쪽을 답으로 출력하되, 승리 확률이 $10^{-6}$ 미만으로 차이가 날 경우에는 무승부임을 알려주면 되는 문제입니다.

풀이

겉보기에는 확률을 계산하고 비교해 주는 문제로 보이지만, 이동하는 방식을 파악하면 그렇지 않은 문제임을 알 수 있습니다. 누가 이기는 지가 처음부터 정해져 있어요. 왜 그런지 지금부터 차근차근 설명해 볼 게요.

이동할 때마다 격자의 바닥 색이 바뀌어요

그림을 보시면 아시겠지만, 나이트가 한 번 이동할 때마다 항상 바닥의 색이 바뀌게 돼요. 흰색 격자에서 이동하면 검은색 격자로 이동하고, 검은색 격자에서 이동하면 흰색 격자로 이동하게 돼요. 이 성질을 기억하고, 다음 단계에서 써 먹어 봅시다.

그림만으로도 충분히 이해가 되시겠지만 그럼에도 왜 색이 항상 바뀌는 지 이해가 되지 않으신다면, 체스판 위에서 상하좌우로 한 칸 이동할 때마다 색이 바뀌고, 나이트의 이동은 세 번 상하좌우로 이동한 것과 같음을 이해하시면 될 것 같아요!

이동을 완료했을 때의 말이 위치한 체스판의 색에 주목하기

이제 본격적으로 문제를 푸는 전략을 생각해 봅시다. 두 말이 위치한 지점의 색에 주목해 보세요.

말을 움직인 후, 상대방의 말의 위치에 있는 색과 내 말의 위치에 있는 색이 서로 다르다는 것은 무슨 의미일까요? 바로 그 상태에서는 내 말이 절대로 상대방의 말로 이동할 수 없음을 의미합니다. 당연하지만 색이 서로 다르니까요. 이 발상을 이용해, 두 말의 시작지점의 색이 같은 경우/다른 경우의 두 가지로 분리해서 생각해 보겠습니다.

1. 두 말의 시작지점의 색이 같은 경우
   백의 이동 - 백이 이동하기 전 두 말이 위치한 지점의 색은 같으므로, 백이 이동한 후에는 백이 위치한 지점의 색이 달라져 두 말이 위치한 지점의 색은 항상 다르게 됩니다. 즉 두 말이 항상 만날 수 없고, 이는 백이 이동을 했을 때 흑이 있는 위치로 이동할 가능성이 없음을 의미합니다.
   
   흑의 이동 - 흑이 이동하기 전 두 말이 위치한 지점의 색은 다르므로, 흑이 이동한 후에는 두 말이 위치한 지점의 색은 항상 같게 됩니다. 흑이 이동을 했을 때 백이 있는 위치로 이동할 가능성이 있습니다.
   
   그리고 이 과정이 계속해서 반복됩니다. 즉 백은 절대로 흑을 만날 수 없지만, 흑은 항상 백을 만날 수 있는 가능성이 있습니다. 따라서 흑이 항상 승리하게 됩니다.
   
   
2. 두 말의 시작지점의 색이 다른 경우
   백의 이동 - 백이 이동하기 전 두 말이 위치한 지점의 색이 다르므로, 백의 이동 후에는 두 말이 위치한 지점의 색이 같습니다. 백이 이길 가능성이 있습니다.
   
   흑의 이동 - 흑의 이동 후 두 말이 위치한 지점이 항상 다르므로, 지금까지의 예시와 같이 흑이 이길 가능성은 없습니다.
   
   이 과정 역시 두 말의 시작지점의 색이 같은 경우와 동일하게 과정이 계속되서 반복되므로, 백이 항상 승리하게 됩니다.

결론

• 시작 시 흑이 위치한 격자의 색과 백이 위치한 격자의 색이 같다면, 흑이 항상 승리합니다.
• 반대로 다르다면, 백이 항상 승리합니다.
• 비기는 경우는 없게 됩니다. 따라서 'draw' 를 정답으로 출력할 일은 없습니다.
• 결국 우리가 알아야 하는 것은 흑, 백이 처음에 위치한 지점의 색이 같은지, 다른지 입니다. 이는 체스판 내에서 상하좌우로 한 번 이동할 때마다 색이 변경됨을 이용해, 두 말의 거리가 짝수인지, 홀수인지를 계산해 판단하면 됩니다.

코드

• Python 3

wr, wc = map(int, input().split())
br, bc = map(int, input().split())

if (abs(br - wr) + abs(bc - wc)) % 2 == 0:
    print('black')
else:
    print('white')