동전 게임

• 그냥 단순하게 현재 상태에서부터 BFS를 돌려서 모두 앞면인 상태나 모두 뒷면인 상태까지 가는데 필요한 최소 연산 횟수를 찾으면 된다.
• 상태를 비트마스크로 표현하면, 세개의 동전을 뒤집는 연산은, 1이 세개 포함된 마스크와 xor하는 것으로 간단히 구현할 수 있다.
• 상태의 갯수는 2^9이고, 각 상태에서는 8개의 연산이 가능하므로, BFS의 시간 복잡도는 O(V+E) = O(2^9 + 2^9*8) 이지만, 어차피 상수이므로 결국은 O(1)로 취급한다.
• 매 테스트 케이스마다 주어진 상태에서 시작하는 BFS를 돌리면 총 T번의 BFS가 필요하다. 그것보다는 맨 처음에 모두 앞면인 상태에서 출발하는 BFS를 한번만 돌리면, 모든 상태들이 모두 앞면으로 바뀌기 위해서 얼마의 연산이 필요한지를 구할수 있다. 그러면 각 테스트케이스에 대해서는 그 구해놓은 값을 바로 사용하기만 하면 된다.
  • 정답을 구하기 위해서는 처음 상태에서 모두 뒷면인 상태로 바꾸기 위한 연산 횟수도 필요하다. 하지만 이는, 처음 상태를 전부 플립한 상태를 만들어서, 그 상태에서 모두 앞면인 상태로 바꾸는 것과 동일하다. 그렇기 때문에 모두 앞면인 상태에 대해서 구한 값을 그대로 활용할 수 있다.
• 이렇게 하면 총 시간 복잡도는 O(T)가 된다.

"""Solution code for "BOJ 9079. 동전 게임".

- Problem link: https://www.acmicpc.net/problem/9079
- Solution link: http://www.teferi.net/ps/problems/boj/9079

Tags: [BFS]
"""

from teflib import search

FLIP_MASKS = (0b111000000, 0b000111000, 0b000000111, 0b100100100, 0b010010010,
              0b001001001, 0b100010001, 0b001010100)
INF = float('inf')


def main():
    dists = search.min_distances(lambda x: [x ^ m for m in FLIP_MASKS],
                                 0b000000000)
    T = int(input())
    for _ in range(T):
        board = [input() for _ in range(3)]
        coins = ' '.join(board).split()
        state = sum(1 << i for i, ch in enumerate(coins) if ch == 'H')
        flipped_state = state ^ 0b111111111
        answer = min(dists.get(state, INF), dists.get(flipped_state, INF))
        print('-1' if answer == INF else answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.search.min_distances