[Python/파이썬] 백준 9079번 동전 게임

9079번: 동전 게임

 

문제

상우는 재미있는 게임을 생각해냈다. 동전 9개를 아래 그림과 같이 3행 3열로 놓는다. H는 앞면, T는 뒷면을 의미한다.

게임의 목적은 이 동전의 모양을 모두 같은 면(H나 T)이 보이도록 하는 것이다. 단, 하나의 동전만을 뒤집을 수는 없고, 한 행의 모든 동전, 한 열의 모든 동전 또는 하나의 대각선 상의 모든 동전을 한 번에 뒤집어야 한다. 그런 식으로 세 개의 동전을 뒤집는 것을 '한 번의 연산'으로 센다. 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다. 오랜 시간 생각한 끝에 위의 경우는 두 번의 연산으로 가능하다는 것을 알아냈고, 또, 이것이 최소인 것도 알아내었다.

또한, 모두 같은 면으로 만드는 것이 불가능한 모양이 있다는 것도 알아내었다. 다음이 그 예이다.

상우를 도울 수 있는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 주어진다.

출력

각 테스트 케이스에 대해서, 모두 같은 면이 보이도록 만들기 위한 최소 연산 횟수를 출력하고, 불가능한 경우에는 -1을 출력한다.

코드

from collections import deque

def flip(coin, m, n = 0):   # 뒤집을 배열, 뒤집는 방법, n번째 줄(대각선일때는 사용X)
    # n번째 행 뒤집기
    if m == 0:
       coin ^= int(0b111000000 >> 3 * n)
    # n번째 열 뒤집기        
    elif m == 1:
        coin ^= int(0b100100100 >> n)
    # 왼위->오른아래 대각선 뒤집기  
    elif m == 2:
        coin ^= int(0b100010001)
    # 오른위->왼아래 대각선 뒤집기
    elif m == 3:
        coin ^= int(0b001010100)
    return coin

# 코인이 모두 같은 면인지 확인
def check(coin):    
    return True if (coin == 0 or coin == 511) else False
    
for _ in range(int(input())):
    coin = 0
    for _ in range(3):  
        for c in list(input().split()):
            coin = coin << 1
            if c == 'H':    # H는 1, T는 0
                coin += 1
                
    # 코인 확인
    visited = [False] * 1000
    visited[coin] = True
    q = deque([[coin, 0]])
    find = False
    while q:
        now, cnt = q.popleft()
        if check(now):
            print(cnt)
            find = True
            break
        for i in range(4):  # 뒤집는 방법
            if i < 2:   # 행 열 뒤집기
                for j in range(3):  # 뒤집을 줄
                    tmp = flip(now, i, j)
                    if not visited[tmp]:
                        q.append([tmp, cnt+1])
                        visited[tmp] = True
            else:   # 대각선 뒤집기
                tmp = flip(now, i)
                if not visited[tmp]:
                    q.append([tmp, cnt+1])
                    visited[tmp] = True
                    
    if not find:
        print(-1)

H는 1, T는 0으로 하여 비트마스킹을 이용하여 풀이하였다.

예를 들어 문제의 예시를 바꿔보자면 다음과 같다.

뒤집기 연산은 XOR 연산을 사용했다. 

•  XOR 연산

비트 1	비트 2	결과값
0	0	0
0	1	1
1	0	1
1	1	0

위의 표를 보면 알 수 있듯이 1과 XOR 연산을 하면 0과 1이 뒤바뀐다. 따라서 뒤집기를 하려는 줄의 숫자들만 1로 한 숫자와 XOR 연산을 하면 뒤집기 연산을 한 효과를 낼 수 있다.

 

flip() 함수에서 n = 0으로 default 값을 준 것은 대각선을 뒤집는 연산일 때는 n값을 넣지 않기 때문에 n은 옵션인 것으로 처리하기 위해 default 값을 넣어주었다. 근데 지금 생각해보니 그렇게 하지 않고 왼쪽위->오른쪽아래 대각선은 0, 오른쪽위->왼쪽아래 대각선 1로 정하고 대각선을 선택하는데 n을 사용했어도 됐을 거 같다.

 

탐색은 BFS를 이용하여 하였다.

• 현재 coin 배치에서 가능한 모든 뒤집기를 해본다. 모든 행, 열, 대각선에 대해 한 줄씩 뒤집기를 해보고 이전에 나온 배치가 아니라면 q에 넣고 visited에 방문처리를 해준다. 이 과정을 q가 빌 때까지 반복한다.
• coin의 배치는 비트마스킹을 이용하여 하였으니 숫자로 나타낼 수 있다. 따라서 visited 배열의 인덱스는 coin의 배치를 비트마스킹한 숫자로 하면 된다.