n × n 크기의 행렬이 하나의 체스판을 나타낸다고 가정해 봅시다. 행렬에는 1과 0만 존재하며, 1은 퀸(Queen)이 있는 칸, 0은 빈 칸을 의미합니다. 우리가 확인해야 할 것은 이 체스판이 N-퀸(N-Queen) 퍼즐의 유효한 해답인지 여부입니다.
N-퀸 문제에서 유효한 해답이 되려면 어떤 두 퀸도 서로를 공격할 수 없는 위치에 있어야 합니다. 즉, 같은 행, 같은 열, 같은 대각선 위에 두 개 이상의 퀸이 존재해서는 안 됩니다.
예를 들어 다음과 같은 입력이 주어졌을 때,
출력 결과는 True가 됩니다.
문제 해결 접근 방식
이 문제는 네 개의 집합(set)을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 같은 행에 있는 퀸들은 행 번호(i)가 동일합니다.
- 같은 열에 있는 퀸들은 열 번호(j)가 동일합니다.
- 같은 ↘ 방향 대각선에 있는 퀸들은 (i − j) 값이 동일합니다.
- 같은 ↗ 방향 대각선에 있는 퀸들은 (i + j) 값이 동일합니다.
따라서 다음 단계로 진행합니다.
- n := 행렬의 행 개수로 설정합니다.
- rows, cols, diags, rev_diags라는 네 개의 빈 집합을 생성합니다.
- 행렬의 모든 칸을 순회하면서 값이 1인 칸(퀸)을 발견하면:
- i를 rows 집합에 추가
- j를 cols 집합에 추가
- (i − j)를 diags 집합에 추가
- (i + j)를 rev_diags 집합에 추가
- 네 집합의 크기가 모두 n과 같으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
집합은 중복 값을 자동으로 제거하기 때문에, 두 퀸이 같은 행·열·대각선에 있다면 해당 집합의 크기가 줄어들게 됩니다. 따라서 최종적으로 모든 집합의 크기가 n이라면 어떤 퀸도 서로 공격하지 않는다는 의미입니다.
구현 예제
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
복잡도 분석
이 알고리즘은 행렬의 모든 칸을 한 번씩 순회하므로 시간 복잡도는 O(n²)이며, 네 개의 집합을 저장하기 위한 공간 복잡도 역시 O(n)입니다. 백트래킹 없이도 기존 배치의 유효성을 빠르게 검증할 수 있는 효율적인 방법입니다.