[Python] 7003번 Checker Board

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

---

 

25/07/03

 

 

이와 거의 똑같은 문제로 왕들의 외나무다리 돌게임이라는 문제가 있는데, 해당 문제를 이전에 해결했음에도 불구하고 문제를 헤맸었다.

---

 

문제 접근 방식:

 

 

결국 줄 별로 게임이 분리된다는 것은 쉽게 관찰할 수 있다.

 

따라서 줄 별로 게임이 어떻게 거동되는지 확인해보자.

 

결론적으로 두 말 사이의 거리만큼의 돌이 존재하는 님게임이라고 볼 수 있다.

 

왜냐하면, 처음에 두 말 사이의 거리가 $n$이라고 해보자. 그러면 선공이나 후공이 거리를 늘리는 행동을 하면, 다른 사람이 똑같은 행동을 해서 거리를 좁힐 수 있기 때문이다. (따라쟁이 전략)

 

따라서 거리가 줄어들면 줄어들었지, 늘어나지는 않는다.

 

즉, 두 말 사이의 거리가 돌의 개수가 되는 님게임으로 간주할 수 있다.

 

여기서 한 가지 예외가 있는데, 말이 한 줄에 하나만 존재하는 경우이다.

 

만약 말 혼자 외딴 줄에 있는 경우가 있다면, 사실상 그 말은 왔다갔다 하면서 무한대의 기회를 가진다.

 

만약 흰색만 그런 말을 가지고 있다면 님게임이랑 상관 없이 흰색이 항상 이긴다.

 

검은색만 그런 말을 가지고 있다면 검은색이 항상 이긴다.

 

만약 둘다 그런 말을 가지고 있다면 항상 비긴다.(왔다 갔다 할 것이므로)

 

이러한 몇 가지 경우들을 제외하고, 만약 모든 말이 서로가 서로에게 마주보는 말이라면? 위에서 이야기한 것 처럼 거리가 하나의 님게임이라고 생각하고 XOR을 취해주면 된다.(이 부분은 왕들의 외나무 다리 돌게임과 똑같다.)

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 7003번 Checker Board
# 스프라그-그런디 정리
'''
접근 방법:
붙은 상태 -> 선공이 뭔짓거리를 해도 짐
따라서 두 말 사이의 거리 = 님게임
만약 말 하나만 있는 행이 있다면
흰색 말 하나만 있는 행이 있고
검은 말 하나만 있는 행은 없다면 -> 님버랑 상관 없이 선공 승
반대면 후공 승
만약 말 하나만 있는 행이 흰색 검은색한테 둘다 있다면 -> 무승부
'''
import sys
input = sys.stdin.readline

def solve():
    M, N, P, Q = map(int, input().split())
    if N <= 1 or M == 0:
        print('B')
        return
    white = [tuple(map(int, input().split())) for _ in range(P)]
    black = [tuple(map(int, input().split())) for _ in range(Q)]
    white.sort()
    black.sort()
    A = []
    white_only, black_only = False, False
    i, j = 0, 0
    while i < max(P, Q) and j < max(P, Q):
        if white[i][0] != black[j][0]:
            if white[i][0] < black[j][0]:
                i += 1
                white_only = True
            else:
                j += 1
                black_only = True
            continue
        A.append(abs(white[i][1]-black[j][1])-1)
        i += 1
        j += 1
    if white[-1][0] != black[-1][0]:
        white_only = True
        black_only = True
    if white_only and black_only:
        print('T')
        return
    if white_only:
        print('W')
        return
    if black_only:
        print('B')
        return
    ans = 0
    for a in A:
        ans ^= a
    print('W' if ans else 'B')
    return

T = int(input())
for _ in range(T):
    solve()