[백준/파이썬] 9079번: 동전 게임 핵심 정리

문제 보기 : https://www.acmicpc.net/problem/9079

 

동전 게임 문제의 핵심 아이디어

3 x 3 보드의 각 칸에 동전들이 놓여져 있는 상태를 받은 다음 특정 행, 열 또는 대각선의 칸을 뒤집어 모든 칸의 동전을 앞면 혹은 뒷면으로 만들어야 합니다.

 

이 문제를 해결하는 단순한 방법은 그저 계속 뒤집어서 모든 면을 앞면(또는 뒷면)으로 만드는 것인데요. 이때 한 상태에서 뒤집는 경우의 수는 총 8가지가 나옵니다.

즉, 각 칸을 0~8 까지로 정의했을 때 한 행을 뒤집는 경우 - (0,1,2),(3,4,5),(6,7,8), 한 열을 뒤집는 경우 - (0,3,6), (1,4,7), (2,5,8), 한 대각선을 뒤집는 경우 - (0,4,8), (2,4,6) 8가지 경우의 수가 존재합니다. 그리고 각 뒤집한 상태마다 또 8가지의 경우의 수가 존재하기 때문에 총 경우의 수는 8^n만큼 많아져 버립니다.

 

그래서 이 문제를 푸는 핵심은 두 가지인데, (1) 이미 해본 적 있는 상태의 경우 또 뒤집어보지 않는 것과, (2) 이미 해 본 적 있는지 여부를 효율적으로 저장해 놓는 것입니다.

 

모든 상태에 대한 경우의 수는 각각의 9칸이 앞/뒷면을 가질 수 있기 때문에 총 2^9(512)가지인데요. 뒤집어서 나온 결과가 이미 해 본 적 있는 상태라면 이를 또 뒤집어보지 않아도 될 것입니다. 그렇다면 특정한 상태가 이미 해 본 적 있는지 여부를 어떻게 저장해 놓으면 좋을까요? 이미 해 본 보드의 상태를 담는 배열을 만들어서 여기에 해당하는 상태가 있는지 확인해 보는 건 어떨까요? 그런데 그렇게 할 경우 파생되는 모든 경우의 수마다 그 배열을 순회하면서 방문 여부를 판단해야 하기 때문에 굉장히 비효율적이라고 할 수 있습니다.

 

이 때, 각 칸이 두 가지 경우의 수를 가지고 있는 점에 착안하여 각 보드 상태를 이진수로 만들고 이를 다시 십진수로 변환하면 각 보드의 상태를 0~511까지의 숫자에 대입시켜 방문 여부를 저장할 수 있습니다. 이를 통해 보다 효율적인 방문 여부를 관리가 가능합니다.

 

 

예시 분석을 통해 이해하기

특정 상태를 0~511의 상태값으로 변환하는 과정

 

각 상태를 받을 때, 앞면(H)은 1로, 뒷면(T)은 0으로 하여 변환한 뒤, 이를 일렬로 나열한다면 특정 상태를 나타내는 이진수를 얻을 수 있는데요. 이를 십진수로 변환한다면 0~511까지의 상태값이 나오는 것입니다.

 

예를 들어 앞면만 있는 경우에 상태값은 이진수 111111111을 변환해 511이 되고, 뒷면만 있는 경우의 상태값은 이진수 000000000를 변환해 0이 됩니다.

 

위의 예시에서 첫번째 행(0,3,6)을 뒤집은 뒤의 상태값을 구하는 과정

 

즉, 어떤 상태에서 8가지 경우의 수로 동전을 뒤집은 뒤, 그 상태값을 구해 0 또는 511이라면 정답 조건을 만족하므로 그동안 뒤집은 수를 반환하고, 아니라면 이미 방문한 상태값인지를 판단해 아직 방문하지 않은 상태라면 그동안 뒤집은 수에 1을 더한 뒤 새롭게 그 상태에 대해 8가지 경우의 수로 뒤집는 것을 반복하면 됩니다.

 

그리고 이 진행 과정을 큐를 통해 관리한다면 뒤집은 수가 작은 상태부터 처리되기 때문에, 자연스럽게 최소로 뒤집은 수를 구할 수 있습니다. 뿐만 아니라 큐가 모두 앞면 또는 뒷면으로 뒤집어지는 수를 구하지 못하고 끝나 버린다면 그렇게 만드는 것이 불가능하다는 것을 의미하므로 -1을 반환하면 됩니다.

 

 

구현하기

보드 → 상태값, 상태값 → 보드 변환 구현 방법을 알고 나면 수월하게 이 문제를 구현할 수 있습니다.

 

먼저 각 칸에 대해 0과 1이 담긴 배열을 받고, 이를 일련의 이진수로 바꾼 뒤 다시 십진수로 바꿔 상태값을 얻는 방법을 알아야 하는데요. 파이썬에서는 이를 내장 함수인 join, int 함수로 간단하게 구현할 수 있습니다.

board = ['1', '0', '0', '1', '0', '0', '0', '1', '1']
print(int(''.join(board), 2))  # 291

 

그 다음으로 알아야 할 것은 상태값을 이진수로 바꾼 뒤 이를 다시 0과 1이 담긴 배열로 바꾸는 방법입니다. 여기서는 파이썬의 내장 함수인 bin, zfill, list를 이용합니다.

 

bin 함수를 통해 십진수를 이진수 문자열로 바꿀 수 있는데, 이진수를 나타내는 표시인 '0b'로 시작되기 때문에 결과값[2:]를 통해 이후의 숫자들만을 얻어와야 합니다. 그런데 이 때 받은 이진수는 앞의 0을 고려하지 않는데요. 0b를 뗐을 때 000000001은 그저 1이 되는 것입니다. 그래서 문자열을 특정한 자리수로 만들 때까지 왼쪽에 0을 채워주는 zfill 함수를 이용해 해당 문자열을 9자리로 만들어 줍니다.

 

그리고 또 하나 알아둬야 할 것은, 파이썬의 문자열은 immutable(불변) 타입이기 때문에 수정이 불가하다는 점입니다.즉 위에서 얻은 9자리 문자열에서 0을 1로 바꾸고 1을 0으로 바꾸고 할 수 없습니다. 그래서 이 문자열을 list 함수를 통해 각 칸에 따라 0과 1이 담긴 배열인 기존 board와 같은 모양으로 만들어 주어야 비로소 8가지 경우에 따라 뒤집어 볼 수 있게 됩니다.

binValue = 291
print(list(bin(binValue)[2:].zfill(9)))  # ['1', '0', '0', '1', '0', '0', '0', '1', '1']

 

위의 두 가지 변환법을 이용하면 이제 문제를 풀 수 있습니다. 우선 보드판 세 줄을 기준으로 0과 1이 담긴 배열을 만들고 이를 상태값으로 바꿔서 해당 상태값에 대해 방문 처리를 한 후, 뒤집은 횟수 0과 함께 큐에 추가해 줍니다.

 

이후 큐에서 하나씩 꺼내서 모든 칸의 동전이 앞면 또는 뒷면인 경우 그 횟수를 반환하고 아닌 경우 상태값을 다시 0과 1의 배열로 변환한 뒤 8가지 경우에 따라 이를 뒤집어 보면 됩니다.

 

그리고 각각의 뒤집은 결과가 아직 해 본 적 없는 상태라면 방문 처리를 한 후 뒤집은 횟수를 증가시켜 큐에 추가합니다. 그러면 자연스럽게 모든 칸의 동전을 앞면 또는 뒷면으로 뒤집는 최소 횟수가 반환될 것이고, 불가능하다면 -1이 반환됩니다.

 

이를 구현한 것은 아래 코드와 같습니다.

import copy
from collections import deque

cases = [(0,1,2), (3,4,5), (6,7,8), (0,3,6), (1,4,7), (2,5,8), (0,4,8), (2,4,6)]

def flip(array, numbers):
    newArray = copy.deepcopy(array)
    for number in numbers:
        if newArray[number] == '1':
            newArray[number] = '0'
        else:
            newArray[number] = '1'
    return newArray

def cal_min_flip(board):
    visited = [False] * 512
    initBinValue = int(''.join(board), 2)
    visited[initBinValue] = True
    
    q = deque()
    q.append((initBinValue, 0))
    
    while q:
        binValue, count = q.popleft()
        # 모든 칸의 동전이 앞면 또는 뒷면인 경우 뒤집은 횟수를 반환
        if binValue == 0 or binValue == 511:
            return count
        # 상태값을 9자리 배열로 변환 후 각 경우에 따라 뒤집기
        binArray = list(bin(binValue)[2:].zfill(9))
        for case in cases:
            flippedBinArray = flip(binArray, case)
            flippedBinValue = int(''.join(flippedBinArray), 2)
            # 아직 해 본 적 없는 경우라면 방문 처리 후 뒤집은 횟수를 증가시켜 큐에 추가
            if not visited[flippedBinValue]:
                visited[flippedBinValue] = True
                q.append((flippedBinValue, count + 1))
                
    return -1

tc = int(input())
for _ in range(tc):
    board = []
    for _ in range(3):
        line = list(input().split())
        for i in range(3):
            if line[i] == 'H':
                board.append('1')
            else:
                board.append('0')
                
    print(cal_min_flip(board))