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

문제

Given a m x n binary matrix mat. 
In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). 
A pair of cells are called neighbors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

A binary matrix is a matrix with all cells equal to 0 or 1 only.

A zero matrix is a matrix with all cells equal to 0.

• m*n 사이즈의 이진 2d 배열이 주어진다.
• 한 값을 뒤집으면 ( 0 > 1 혹은 1 > 0 ) 그 값에 위, 아래, 양 옆의 값도 뒤집어진다.
• 모든 배열의 값이 0이 되게 하기위한 최소한의 뒤집는 횟수를 구하여라

예시

[[0, 0], [0, 1]] 의 경우

제한

• $m == mat.length$
• $n == mat[i].length$
• $1 <= m, n <= 3$
• mat[i][j] 의 값은 반드시 0 혹은 1이다.

풀이

• 제한을 보면 알수 있듯이, 이 2d 배열의 크기는 아무리 커도 3 * 3 이 최대이다.
• bfs를 통해 모든 경우의 수를 탐색하면 된다.
• 단 visited를 통해 중복된 상태가 탐지 될 경우 이 상태는 이미 처리되었다고 가정하고 넘겨야 최적화를 할수 있다.

from typing import List, Tuple

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
    # 양 옆, 위, 아래를 뒤집는 함수
        def flip(mat, row, col) -> None:
            for r, c in [(row, col), (row-1, col), (row+1, col), (row, col-1), (row, col+1)]:
                if 0 <= r < len(mat) and 0 <= c < len(mat[0]):
                    mat[r][c] ^= 1
                    
        # 모든 경우의 수를 탐색하기 위한 BFS
        def bfs(mat) -> int:
        ## BFS를 위한 큐
            queue: List[Tuple[List[List[int]], int]] = [(mat, 0)]
       	## 중복 상태를 방지하기 위한 set
            visited = {str(mat)}
            while queue:
                curr, steps = queue.pop(0)
                # 모두 0이면 바로 리턴
                if all(all(cell == 0 for cell in row) for row in curr):
                    return steps
                # 모든 뒤집을 수 있는 수에 대해 탐색한다.
                for r in range(len(mat)):
                    for c in range(len(mat[0])):
                        temp = [row[:] for row in curr]
                        flip(temp, r, c)
                        # 한번도 나오지 않은 상태일 경우에만 참고한다.
                        if str(temp) not in visited:
                            visited.add(str(temp))
                            queue.append((temp, steps+1))
            return -1