N×N 크기의 이진 행렬이 있다고 가정해 보겠습니다. 여기서 0은 빈 셀(empty cell), 1은 막힌 셀(blocked cell)을 의미합니다. 이때 모든 행과 모든 열에 최소 하나의 선택된 셀이 포함되도록 N개의 빈 셀을 선택하는 방법의 수를 구해야 합니다. 답이 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
문제 예시
예를 들어 입력이 다음과 같다고 해보겠습니다.
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
이 경우 출력은 4입니다. x를 선택된 셀이라고 할 때, 조건을 만족하는 배치가 총 4가지 존재하기 때문입니다.
접근 방법
이 문제는 백트래킹(backtracking)과 비트마스크(bitmask)를 조합하면 효율적으로 해결할 수 있습니다. 첫 번째 행부터 마지막 행까지 차례대로 내려가면서, 현재 행에서 선택할 수 있는 빈 셀(열)을 하나씩 골라보고, 이미 선택된 열은 비트마스크에 기록해 두어 같은 열이 중복해서 선택되지 않도록 합니다.
구체적인 절차는 다음과 같습니다.
- n := 행렬의 크기
- f(i, bs) 함수를 정의합니다. i는 현재 처리 중인 행, bs는 지금까지 사용된 열 정보를 담은 비트마스크입니다.
- i >= n이면 모든 행을 성공적으로 처리한 것이므로 1을 반환합니다.
- ans := 0으로 초기화합니다.
- j를 0부터 n-1까지 반복하며 다음을 확인합니다.
- matrix[i][j]가 0(빈 셀)이고, bs의 j번째 비트가 0(아직 사용하지 않은 열)이라면 ans := ans + f(i + 1, bs OR 2^j)를 수행합니다.
- ans를 반환합니다.
- 메인 메서드에서 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
동작 원리 정리
재귀 함수 f는 각 행마다 선택 가능한 열을 하나씩 시도하며, 비트마스크 bs 덕분에 동일한 열이 두 번 선택되는 경우를 자동으로 걸러냅니다. 마지막 행까지 모든 셀을 무사히 배치하면 유효한 배치 1개를 카운트하는 방식입니다. 이렇게 하면 행렬에 막힌 셀이 얼마나 많든, '각 행과 열에 최소 하나의 선택된 셀'이라는 조건을 만족하는 모든 배치의 개수를 정확하게 계산할 수 있습니다.