(Python/🥈2)백준리즘알고즘 9079번 : 동전 게임

문제 바로가기 

 

문제:

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

1152

738

564

65.965%

문제

상우는 재미있는 게임을 생각해냈다. 동전 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을 출력한다.

 

풀이:

 

실버인데 좀 쉽지 않은 문제여서 올려본다.

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

t = int(input())
move = [(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(change_arr, new_arr):
    for i in change_arr:
        new_arr[i] = '0' if new_arr[i] == '1' else '1'
    return new_arr


def bfs(numbers):
    visited = [False] * 512
    visited[int(''.join(numbers), 2)] = True

    Q = deque([(int(''.join(numbers), 2), 0)])
    while Q:
        n_num, count = Q.popleft()
        if n_num == 0 or n_num == 511:
            return count

        for number in move:
            n_numbers = flip(number, list(bin(n_num)[2:].zfill(9)))
            n_num_bin = int(''.join(n_numbers), 2)
            if not visited[n_num_bin]:
                visited[n_num_bin] = True
                Q.append((int(''.join(n_numbers), 2), count + 1))

    return -1


for _ in range(t):
    numbers = ("".join(sum([list(map(str, sys.stdin.readline().rstrip().split())) for _ in range(3)], []))
               .replace("H", "1")
               .replace("T", "0"))
    print(bfs(numbers))

 

 

비트마스킹을 위해 0과 1 로 바꿔주고

 

뒤집는 함수를 만들어준다.

 

BFS를 진행하다가 다 뒤집혔을때 종료해준다.