BOJ 10472 - 십자뒤집기

문제

백준 온라인 저지 - 10472번

풀이 과정

보드의 최종 상태가 주어질 때, 초기 상태에서 해당 목표 상태에 도달하기 위한 최소 조작 횟수를 구하는 문제입니다.

이를 위해서 BFS 를 이용해 보드의 모든 가능한 상태를 순회해줍니다.
다만 중복된 상태 순회를 피하기 위해서 보드가 검은색으로 칠해져 있을 경우 1 로, 그렇지 않을 경우 0 으로 변환하여

이진수를 생성한 다음, 중복된 상태를 검증합니다.

코드

import sys
import copy
from collections import deque


dx = [0, 1, -1, 0, 0]
dy = [0, 0, 0, 1, -1]


def convert_board(board, x, y):
    ret = copy.deepcopy(board)

    for i in range(5):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < 3 and 0 <= ny < 3:
            ret[nx][ny] = '*' if ret[nx][ny] == '.' else '.'

    return ret


def convert_to_binary(board):
    binary_str = ''

    for x in range(3):
        for y in range(3):
            binary_str += '0' if board[x][y] == '.' else '1'

    return int(binary_str, 2)


def bfs(goal):
    time = 0
    init_board = [['.'] * 3 for _ in range(3)]
    visit = [0] * 1000

    q = deque([init_board])
    visit[convert_to_binary(init_board)] = 1

    while q:
        loop = len(q)
        for _ in range(loop):
            board = q.popleft()
            if board == goal:
                return time

            for row in range(3):
                for col in range(3):
                    next_board = convert_board(board, row, col)
                    binary_code = convert_to_binary(next_board)

                    if not visit[binary_code]:
                        q.append(next_board)
                        visit[binary_code] = 1

        time += 1


def solution(testcase):
    time = bfs(testcase)

    return time


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        testcase = [list(sys.stdin.readline().strip()) for _ in range(3)]
        answer = solution(testcase)
        print(answer)