[백준/파이썬][Gold V] 보드게임 - 32249

[Gold V] 보드게임 - 32249

문제 링크

성능 요약

메모리: 279300 KB, 시간: 736 ms

분류

게임 이론, 구현

제출 일자

2025년 2월 15일 15:07:29

문제 설명

Alice와 Bob은 두 명이서 보드게임을 진행하려고 한다. 이 보드게임은 어떤 양의 정수 N$N$, M$M$에 대해 총 2NM$2NM$장의 카드를 가지고 진행한다. 이 카드들 중 정확히 NM$NM$장의 카드에는 알파벳 A가, 나머지 NM$NM$장의 카드에는 알파벳 B가 적혀 있다. Alice와 Bob은 게임이 시작하기 전 각자 NM$NM$장의 카드를 적당히 나누어 가져가고, 각자의 앞에 N×M$N\times M$ 모양으로 카드를 배치한다. Alice와 Bob은 서로의 카드 배치를 알고 있다.

게임의 첫 턴은 Alice가 시작한다. 각 플레이어는 자신의 턴에 자신 앞에 있는 M$M$개의 열 중 하나를 고른 후, 그 열에 놓인 가장 위쪽의 카드를 제거한다. 이때 제거한 카드에 적힌 알파벳이 A이면 다음 턴을 Alice가 진행하며, B이면 다음 턴은 Bob이 진행한다. 각 플레이어는 자신의 턴에 카드를 제거해야 하므로, 카드가 비어 있는 열은 고를 수 없다. 또한 어떤 턴에 플레이어가 카드를 제거함으로써 앞에 놓인 카드가 전부 제거된다면, 즉시 그 플레이어가 승리한다.

Alice와 Bob은 서로 이기기 위해 최선을 다한다. 두 사람은 카드의 배치가 주어졌을 때 게임의 승자가 누가 될지 궁금해 하고 있다. 또한 이 배치로부터 시작해, Alice와 Bob이 자신 앞에 놓인 카드를 하나씩 골라 선택한 두 카드를 교환할 때마다 게임의 승자가 어떻게 바뀌는지도 궁금해하고 있다. 이때 카드의 교환은 누적되어 적용된다.

초기 카드 배치와 어떤 두 카드가 교환되는 시행이 주어질 때마다 게임의 승자를 알아내는 프로그램을 작성해 이들의 궁금증에 답해 주자!

입력

첫째 줄에 양의 정수 N$N$, M$M$이 공백을 사이에 두고 주어진다. (1≤N≤10$1\leq N\leq 10$; 1≤M≤1000000$1\leq M\leq 1\, 000\, 000$; NM≤1000000$NM\leq 1\, 000\, 000$)

둘째 줄부터 N$N$개의 줄에 걸쳐 Alice의 카드 배치가 주어진다. (i+1)$(i+1)$번째 줄에는 Alice의 i$i$행에 놓인 카드들의 배치가 주어진다.

 (N+2)$(N+2)$째 줄부터 N$N$개의 줄에 걸쳐 Bob의 카드 배치가 주어진다. (i+N+1)$(i+N+1)$번째 줄에는 Bob의 i$i$행에 놓인 카드들의 배치가 주어진다.

각 행에 놓인 카드들의 배치는 길이 M$M$의 A와 B로만 구성된 문자열이며, i$i$행 j$j$열의 문자는 각 플레이어의 i$i$행 j$j$열의 카드에 쓰여 있는 알파벳을 의미한다.

입력으로 주어지는 문자열은 총 NM$NM$개의 A와 NM$NM$개의 B로 구성되어 있으며, 각 플레이어의 카드 배치의 1$1$행은 각 열에서 가장 위쪽의 카드이다.

 (2N+2)$(2N+2)$째 줄에는 카드가 교환되는 시행의 횟수를 나타내는 양의 정수 Q$Q$가 주어진다. (1≤Q≤200000$1\leq Q\leq 200\, 000$)

 (2N+3)$(2N+3)$째 줄부터 Q$Q$개의 줄에 걸쳐 카드 위치를 바꾸는 시행의 정보가 주어진다. (i+2N+2)$(i+2N+2)$째 줄에는 i$i$째 시행을 나타내는 4$4$개의 정수 r1$r_1$, c1$c_1$, r2$r_2$, c2$c_2$가 공백을 사이에 두고 주어진다. (1≤r1,r2≤N$1\leq r_{1},r_{2}\leq N$; 1≤c1,c2≤M$1\leq c_{1},c_{2}\leq M$) (r1,c1)$(r_1,c_1)$은 교환할 Alice의 카드 위치이며, (r2,c2)$(r_2,c_2)$는 교환할 Bob의 카드 위치이다.

출력

첫째 줄에 주어진 카드의 초기 배치에서 승리하는 플레이어의 이름을 Alice 혹은 Bob으로 출력한다.

둘째 줄부터 Q$Q$개의 줄에 걸쳐 카드 위치를 바꾸었을 때 승리하는 플레이어의 이름을 같은 형식으로 출력한다. (i+1)$(i+1)$째 줄에는 초기 상태에서 첫째 시행부터 i$i$째 시행까지 적용된 카드 배치에서 승리하는 플레이어의 이름을 출력한다.

풀이

import sys
input = sys.stdin.readline

def sol_32249() :
    N, M = map(int, input().split())
    Alice = [list(input().rstrip()) for _ in range(N)]
    Bob = [list(input().rstrip()) for _ in range(N)]

    alice_bottom_b_cnt = Alice[-1].count('B')
    bob_bottom_a_cnt = Bob[-1].count('A')
    print('Alice' if alice_bottom_b_cnt > 0 or bob_bottom_a_cnt == 0 else 'Bob')

    q = int(input())
    for _ in range(q) :
        r1, c1, r2, c2 = [int(x) - 1 for x in input().split()]
        alice_card, bob_card = Alice[r1][c1], Bob[r2][c2]
        if alice_card != bob_card :
            diff = 1 if alice_card == 'A' else -1
            if r1 == N - 1 :
                alice_bottom_b_cnt += diff
            if r2 == N - 1 :
                bob_bottom_a_cnt += diff

        Alice[r1][c1], Bob[r2][c2] = bob_card, alice_card

        print('Alice' if alice_bottom_b_cnt > 0 or bob_bottom_a_cnt == 0 else 'Bob')

sol_32249()

승리 조건에 대해서 생각해보자

1. 마지막에 상대 카드가 있으면 한 턴을 스킵하는 성질이 있음.
   1. 마지막에는 무슨 카드가 있던 제거하면 그 즉시 승리이기 때문에 되도록 상대 카드가 오는 것이 승리 공식일 거라 생각함.
2. Alice가 먼저 턴을 시작하기 때문에 A가 유리하게 시작함. 그래서 조건도 Alice가 유리하게 설정할 수 밖에 없음.
3. Alice의 바닥에 놓여있는 B카드의 개수와 Bob의 바닥에 놓여있는 A카드가 상대에게 턴을 넘기는 기믹이 발동하는 조건이다.
   1. 그러나 이 카드가 마지막 카드라면, 상대에게 턴을 넘기더라도 직전에 턴을 소유하고 있었던 사람이 승리하게 되는 게임.
4. 이 부분을 잘 생각해보자. (나는 못했다)

만약, 전부 다 자신의 카드(Alice : A, Bob : B)만 소지하고 있을 경우, 생각해보면 무조건 Alice의 승리. 왜냐하면 Alice가 먼저 시작하기 때문이다. 

하나를 교환해보자.

Alice는 위의 카드를, Bob은 바닥 카드를 서로 교환하게 되면, Alice는 마지막 카드를 제거 하기 직전, Bob에게 턴을 넘겨줘야 한다. 그리고 Bob은 마지막 카드를 제거하면서 Alice에게 턴을 넘겨줄 것이다. 

위 내용을 if 문에 담으면 이 문제는 생각보다 쉽게 풀린다. 

이를 단순화 하여, Alice의 카드집 바닥에 놓여있는 B카드와 Bob의 카드집 바닥에 놓여있는 A카드의 개수를 비교하자.

내가 가장 먼저 말했던 첫 번째 조건, 각자가 각자의 카드만 가지고 있을 경우, Bob의 바닥 카드에 A가 없을 경우와 동일시 될 수 있다.

이제 하나씩 교환해보면서 경우의 수를 따져보자.

Alice의 바닥 카드가 1개 이상 있으면, 마지막에 그 카드를 제거 하면서 게임을 승리하게 된다. 그래서 Alice는 바닥에 있는 카드가 B카드면 더욱 유리하다. 

생각해보니까 바닥 카드에 1개 이상 있으면 무조건 Alice가 이긴다. A, B카드의 개수가 정해져 있기 때문에 다른 조건을 크신경쓰지 않아도 된다(내가 A를 다 가지고 있으면, 상대가 B를 다 가지고 있다.). 상대 카드를 제거하면서 승리로 게임을 종료하게 되면 되기 때문에 무슨 짓을 하건 Alice가 카드 바닥에 B가 하나 이상 깔려있게 되면 승리하게 되는 게임이다. 

따라서, Alice의 카드집 바닥에 B카드가 하나도 놓여있지 않고(AND) Bob의 카드집 바닥에 A가 하나라도 있으면 => 이것이 유일한 Bob의 승리 조건이다. 

따라서 

print('Alice' if alice_bottom_b_cnt > 0 or bob_bottom_a_cnt == 0 else 'Bob')

이 수식이 성립하게 되는 것이다. 이 풀이는 사실 이 글을 적으면서 생각했다. 기존에 생각해서 풀었던 분들에게 경의를 표한다.