문제 설명#
N-Queens II - LeetCode
N × N 체스판에 N개의 퀸(Queen) 을 배치하는 유효한 방법의 개수를 찾는 문제입니다.
✅ 제약 조건
- 퀸은 서로 공격할 수 없음 (같은 행, 같은 열, 같은 대각선 배치 불가)
- 1 ≤ N ≤ 9
- 가능한 배치 방법의 개수만 반환하면 됨
✅ 출력 형식
1️⃣ 브루트포스 (O(N!)) → 비효율적#
- 모든 경우를 완전 탐색하며 배치 가능 여부를 확인
- N! 개의 경우의 수 발생
- 비효율적이므로 사용하지 않음
2️⃣ 백트래킹 (Backtracking, O(N!)) [추천]#
- DFS(깊이 우선 탐색) + 가지치기(Pruning) 사용
- 퀸을 하나씩 배치하며, 유망하지 않은 경우 즉시 백트래킹
- O(N!)으로 해결 가능하며, N이 작을 경우 빠르게 동작
✔ 배열을 사용하여 퀸 배치 유효성 검사
cols: 각 열에 퀸이 있는지 여부diag1 (↘ 대각선): row + col 값이 같은지 여부diag2 (↙ 대각선): row - col 값이 같은지 여부
코드 풀이#
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| def totalNQueens(n):
def backtrack(row):
if row == n: # 모든 퀸 배치 완료 시 경우의 수 증가
nonlocal count
count += 1
return
for col in range(n):
if col in cols or (row + col) in diag1 or (row - col) in diag2:
continue # 같은 열, 같은 대각선이면 배치 불가능
# 퀸 배치
cols.add(col)
diag1.add(row + col)
diag2.add(row - col)
backtrack(row + 1) # 다음 행으로 이동
# 백트래킹 (배치 취소)
cols.remove(col)
diag1.remove(row + col)
diag2.remove(row - col)
count = 0
cols, diag1, diag2 = set(), set(), set() # 열과 대각선 기록
backtrack(0)
return count
|
Javascript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| var totalNQueens = function(n) {
let count = 0;
let cols = new Set(), diag1 = new Set(), diag2 = new Set();
function backtrack(row) {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;
cols.add(col);
diag1.add(row + col);
diag2.add(row - col);
backtrack(row + 1);
cols.delete(col);
diag1.delete(row + col);
diag2.delete(row - col);
}
}
backtrack(0);
return count;
};
|
참고 및 출처#
programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform