[알고리즘] BOJ 9079 동전 게임 #Python

[BOJ] 9079 동전 게임 바로가기

📍 문제

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

H T T
H T T
T H H

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

H T T   T T T   T T T
H T T → T T T → T T T
T H H   H H H   T T T

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

T H H
H H H
H H H

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

---

📍 입력

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

---

📍 출력

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

---

📍 풀이

✏️ 문제 풀이

BFS 알고리즘을 활용하여 문제를 해결하였다. 그래프 탐색 알고리즘에서 visited 는 무한 루프를 방지하고, 이미 방문한 노드를 다시 처리하지 않기 위해서 사용한다. [동전 게임] 문제에서 정의된 노드는 3 * 3 크기로 구성된 동전의 배열이다. 3 * 3 크기의 배열을 키 값으로한 visited 를 만들게 될 경우 처리하는데 오랜 시간이 사용되기 때문에 동전의 배열을 이진 마스크를 변환하여 visited 배열을 구성하였다.

동전의 배치에 이진 마스크를 적용해보면 다음과 같다.

H T T     1 0 0
H T T  →  1 0 0  →  100100011  →  291
T H H     0 1 1

즉, 동전의 배치로 만들어 질 수 있는 모든 경우의 수는 0(000000000) ~ 511(111111111) 총 512개이다.

BFS 연산 중 조건 달성

if arrBin == 0 or arrBin == 511:
	return count

• arrBin 은 3 * 3 배열의 값을 이진화한 정수 값을 의미한다.
• arrBin 의 값이 0 이라는 것은 배열의 값이 000000000 이라는 것이고 모든 동전이 일치하는 상태이므로 연산을 종료한다.
• arrBin 의 값이 511 이라는 것은 배열의 값이 111111111 이라는 것이고 모든 동전이 일치하는 상태이므로 연산을 종료한다.

✍ 전체 코드

# BOJ 9079 동전 게임
# https://www.acmicpc.net/problem/9079

from sys import stdin
from collections import deque

def solution(arr):

    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)]

    visited = [False] * 512
    visited[int(''.join(arr), 2)] = True
	# BFS
    queue = deque([(int(''.join(arr), 2), 0)])
    while queue:
        arrBin, count = queue.popleft()

        if arrBin == 0 or arrBin == 511:
            return count

        for numbers in cases:
            newArr = flip(numbers, list(bin(arrBin)[2:].zfill(9)))
            vs = int(''.join(newArr), 2)
            if not visited[vs]:
                visited[vs] = True
                queue.append((int(''.join(newArr), 2), count+1))
    
    return -1

def flip(numbers, arr):
    for num in numbers:
        arr[num] = '0' if arr[num] == '1' else '1'
    return arr

T = int(stdin.readline())

for _ in range(T):
    arr = list(list(stdin.readline().split()) for _ in range(3))
    arr = ['1' if arr[y][x]=='H' else '0' for y in range(3) for x in range(3)]
    print(solution(arr))