파이썬에서 행렬의 빈 셀을 선택할 수 있는 방법의 수를 확인하는 프로그램

0이 빈 셀이고 1이 차단된 셀인 N x N 이진 행렬이 있다고 가정하면 모든 행과 모든 열에 최소한 하나의 선택된 셀이 있도록 N개의 빈 셀을 선택하는 방법의 수를 찾아야 합니다. 대답이 매우 크면 결과 모드 10^9 + 7

따라서 입력이 다음과 같으면

다음 구성이 있으므로 출력은 4가 됩니다(여기서 x는 선택된 셀) -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=행렬의 크기
• f() 함수를 정의합니다. I, bs
• i>=n이면
  • 1을 반환
• ans :=0
• 0~n 범위의 j에 대해
  • 행렬[i, j]이 0과 같고 (2^j AND bs가 0)이면
    • ans :=ans + f(i + 1, bs OR 2^j)
• 반환
• 메인 메소드 호출 및 반환 f(0, 0)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, matrix):
      n = len(matrix)

      def f(i, bs):
         if i >= n:
            return 1
         ans = 0
         for j in range(n):
            if matrix[i][j] == 0 and ((1 << j) & bs == 0):
               ans += f(i + 1, bs | (1 << j))
         return ans

      return f(0, 0)

ob = Solution()
matrix = [
   [0, 0, 0],
   [0, 0, 0],
   [0, 1, 0]
]
print(ob.solve(matrix))

입력

[  
[0, 0, 0],  
[0, 0, 0],  
[0, 1, 0] ]

출력

4