[Python] 동전 게임 (백준 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을 출력한다.

예제 입력 1

3
H T T
H T T
T H H
T H H
H H H
H H H
H H H
H T H
H H H

예제 출력 1

2
-1
4

 

문제 이해

- 문제의 예시와 같이 가로, 세로, 대각선 중 하나를 뒤집는 것을 연산 1회로 규정합니다.

- 최소한의 연산 횟수를 가지며, 모든 면이 같은 면을 만드는 것이 목표입니다.

 

 

문제 풀이

- H와 T 둘 중 하나이기 때문에 0과 1로 치환해서 생각합니다.

- 0과 1로 치환시 3*3배열을 쭉 펼친다고 생각하면 이진수를 얻을 수 있는데, 이 이진수는 케이스마다 겹치는 경우가 없는 유일한 경우입니다. 이를 10진수로 바꿔서 케이스에 대한 key값으로 생각하면 0(000000000)~511(111111111)까지 총 512개의 경우의 수를 얻을 수 있습니다. 다시 말해서 만들 수 있는 모든 경우의 수는 512가지 인 것 입니다.

- 또한 한번 연산을 할 때 0~2행 체크, 0~2열 체크, 대각선 2개 체크로 총 8가지 방법을 사용할 수 있습니다.

- 완전탐색으로 살펴본다고 할 때, 한 정점(노드)에서 8개의 엣지(간선)을 가지는 그래프를 그릴 수 있습니다.

- 여기까지 진행되었다면 이후엔 일반적인 방문처리를 진행하는 BFS와 동일하며, 최단거리를 찾아야 하기 때문에 노드 레벨(연산 횟수)을 함께 기록합니다.

- 이진수와 십진수의 변환 과정에서 정수형을 문자열로 바꾸고 다시 되돌리는 과정만 조심하면 될 것 같습니다.

 

코드

# 백준 9079 동전게임
from collections import deque

def make_bin(arr: list):  # 배열->2진수 생성
    a = []
    for i in arr:
        for j in i:
            a.append(j)
    n = int(''.join(map(str, a)), 2)
    return n

t = int(input())
for _ in range(t):
    input_arr = [list(map(str, input().split())) for _ in range(3)]
    # 'H' -> 1 / 'T' -> 0
    arr = []
    for k in range(3):
        new_arr = list(map(lambda v: 1 if v == 'H' else 0, input_arr[k]))
        arr.append(new_arr)

    cases = [[0, 3, 6], # 열 탐색
            [1, 4, 7],
            [2, 5, 8],
            [0, 1, 2],  # 행 탐색
            [3, 4, 5],
            [6, 7, 8],
            [2, 4, 6],  # 대각선 탐색
            [0, 4, 8]]

    visited = [False]*512
    q = deque()
    bin_n = make_bin(arr)  # 정수
    q.append((bin_n, 0))  # 배열을 2진수로 바꿔서 큐에 넣음
    visited[bin_n] = True  # 시작 노드 방문처리
    answer = -1

    while q:
        num, cnt = q.popleft()
        if num == 0 or num == 511:
            answer = cnt
            break
        for case in cases:
            b_num = list(bin(num)[2:].zfill(9))

            for c in case:
                b_num[c] = '0' if b_num[c] == '1' else '1'
            chngd_num = int(''.join(b_num), 2)

            if not visited[chngd_num]:
                visited[chngd_num] = True
                q.append((chngd_num, cnt+1))

    print(answer)

 

완전탐색 유형으로 분류되어 실버2 난이도로 설정된 것 같은데, 체감 난이도는 골드4,5 정도 되는 것 같습니다. 최근 만나본 문제 중 가장 어려웠습니다 ㅠ..