체스 판을 나타내는 n x n 행렬이 있다고 가정합니다. 1과 0이 있는데 1은 퀸을, 0은 빈 셀을 나타냅니다. 보드가 N-Queen 퍼즐에 대한 유효한 솔루션인지 여부를 확인해야 합니다. 우리가 알고 있듯이 보드는 두 개의 퀸이 서로 공격하지 않는 유효한 N-퀸 솔루션의 솔루션입니다.
따라서 입력이 다음과 같으면
그러면 출력은 True
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다.
- n :=행렬의 행 수
- rows :=새 집합, cols :=새 집합, diags :=새 집합, rev_diags :=새 집합
- 0에서 n 사이의 i에 대해
- 0에서 n 사이의 j에 대해 다음을 수행합니다.
- 행렬[i, j]가 1이면
- 행에 i 삽입
- 열에 j 삽입
- 진단에 (i - j) 삽입
- rev_diags에 (i + j) 삽입
- 행렬[i, j]가 1이면
- 0에서 n 사이의 j에 대해 다음을 수행합니다.
- 행의 크기, 열의 크기, diags의 크기, rev_diags의 크기가 n과 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예
class Solution: def solve(self, matrix): n = len(matrix) rows = set() cols = set() diags = set() rev_diags = set() for i in range(n): for j in range(n): if matrix[i][j]: rows.add(i) cols.add(j) diags.add(i - j) rev_diags.add(i + j) return len(rows) == len(cols) == len(diags) == len(rev_diags) == n ob = Solution() matrix = [ [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0] ] print(ob.solve(matrix))
입력
matrix = [ [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0] ]
출력
True