1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

[zeikar]

Problem link

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

Problem Summary

자신과 상하좌우 4개 비트를 반전시킬 수 있을 때 모든 비트를 0으로 만드는 최소 횟수를 구하는 문제.

Solution

딱 보니 배열 크기도 작고 최소 횟수이므로 BFS로 돌려주면 된다.

하나 까다로운 것은 2차원 리스트를 큐나 방문 set에 넣고 빼고 하는 것인데.. set에 넣기 위해 tuple로 바꾸고...수정하기 위해 리스트로도 바꾸고... 좀 복잡하게 구현하긴 하였다.

Source Code

import copy
from typing import List


class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])

        def to_tuple(matrix):
            return tuple(tuple(row) for row in matrix)

        def tuple_to_matrix(tuple_matrix):
            return [list(row) for row in tuple_matrix]

        queue = [(mat, 0)]
        visited = set()
        visited.add(to_tuple(mat))
        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        while queue:
            mat, step = queue.pop(0)

            if all(mat[i][j] == 0 for i in range(n) for j in range(m)):
                return step

            for i in range(n):
                for j in range(m):
                    copy_mat = tuple_to_matrix(mat)
                    copy_mat[i][j] = 1 - mat[i][j]
                    for d in direction:
                        x, y = i + d[0], j + d[1]
                        if 0 <= x < n and 0 <= y < m:
                            copy_mat[x][y] = 1 - mat[x][y]

                    tuple_matrix = to_tuple(copy_mat)
                    if tuple_matrix not in visited:
                        queue.append((tuple_matrix, step + 1))
                        visited.add(tuple_matrix)

        return -1