[BOJ/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을 출력한다.

풀이

from collections import deque

t = int(input())

def bfs(graph):
    def check_all(graph): 
        first = graph[0][0]
        for i in range(3):
            for j in range(3):
                if graph[i][j] != first:
                    return False
        return True

    def graph_to_string(graph):
        return ''.join(''.join(row) for row in graph)

    start = graph_to_string(graph)
    visited = set([start])
    queue = deque([(graph, 0)])

    while queue:
        current_graph, count = queue.popleft()

        if check_all(current_graph):
            return count

        for i in range(3):
            # 행 뒤집기
            # 2차원 리스트 복제
            temp = [row[:] for row in current_graph]
            for j in range(3):
                if current_graph[i][j] == "H":
                    temp[i][j] = "T"
                else:
                    temp[i][j] = "H"
            new_graph_str = graph_to_string(temp)
            if new_graph_str not in visited:
                visited.add(new_graph_str)
                queue.append((temp, count + 1))

            # 열 뒤집기
            temp = [row[:] for row in current_graph]
            for j in range(3):
                if current_graph[j][i] == "H":
                    temp[j][i] = "T"
                else:
                    temp[j][i] = "H"
            new_graph_str = graph_to_string(temp)
            if new_graph_str not in visited:
                visited.add(new_graph_str)
                queue.append((temp, count + 1))

        # 왼쪽 위 -> 오른쪽 아래 대각선 뒤집기
        temp = [row[:] for row in current_graph]
        for i in range(3):
            if current_graph[i][i] == "H":
                temp[i][i] = "T"
            else:
                temp[i][i] = "H"
        new_graph_str = graph_to_string(temp)
        if new_graph_str not in visited:
            visited.add(new_graph_str)
            queue.append((temp, count + 1))

        # 오른쪽 위 -> 왼쪽 아래 대각선 뒤집기
        temp = [row[:] for row in current_graph]
        for i in range(3):
            if current_graph[i][2 - i] == "H":
                temp[i][2 - i] = "T"
            else:
                temp[i][2 - i] = "H"
        new_graph_str = graph_to_string(temp)
        if new_graph_str not in visited:
            visited.add(new_graph_str)
            queue.append((temp, count + 1))

    return -1

for _ in range(t):
    graph = [list(input().split()) for _ in range(3)]
    print(bfs(graph))

 

1. check_all 함수: 그래프의 모든 값이 같은 값인지 확인한다. 첫번째 값을 가지고 모든 원소가 같으면 True 를 리턴
2. graph_to_string 함수: 방문 처리에 2차원 배열 넣으려다가 머리 깨고 새로운 방법.. 그래프의 값을 string 값으로 뭉쳐서 방문 처리 해줬다.
3. 행 단위 뒤집기, 열 단위 뒤집기, 대각선 각 방향(좌->우, 우->좌) 단위 뒤집기 모두 반복문을 돌면서 큐에 넣음
   -> T이면 H, H이면 T로 변환 후 방문 처리용 값 생성
4. 방문 처리 해주고 큐에서 넣고 빼고 하면서 bfs 수행, 실패 시 -1 리턴하고 성공 시 count 값만 리턴
5. t회 돌면서 graph 값을 추가해주고 bfs 함수 결과 출력

이거 문제 너무 어려웠다 구글링해도 무슨 비트마스킹..? 방법만 알려주고 지피티도 마찬가진데 솔직히 봐도 몬말인지 몰?루?

나중에 붙잡고 공부해야 할 듯; 그냥 아는 방법으로 돌아돌아 풀었다 어려운 bfs 문제 같았음 나에겐