mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-01 18:55:23 +08:00
Yudong Jin
2f561d3d51
* feat(ko): add the complete Korean online edition * Use UTF-8 for Python CI output on Windows * Remove print-book promotion from the Korean site * fix(ko): preserve emphasis before Korean particles
54 lines
4.1 KiB
Markdown
54 lines
4.1 KiB
Markdown
# n-퀸 문제
|
|
|
|
!!! question "문제"
|
|
|
|
체스 규칙에서 퀸은 같은 행, 열 또는 대각선에 있는 말을 공격할 수 있다. 퀸 $n$ 개와 $n \times n$ 크기의 체스판이 주어졌을 때, 퀸들이 서로 공격할 수 없도록 배치하는 방법을 찾아라.
|
|
|
|
아래 그림과 같이 $n = 4$이면 해는 두 개다. 백트래킹 관점에서 $n \times n$ 체스판의 $n^2$ 개 칸은 모든 선택지 `choices`를 제공한다. 퀸을 하나씩 놓는 동안 체스판은 계속 바뀌며, 각 시점의 체스판이 상태 `state`다.
|
|
|
|
|
|
|
|
아래 그림은 세 가지 제약 조건을 보여 준다. **여러 퀸이 같은 행, 같은 열, 같은 대각선에 있으면 안 된다**. 대각선은 주대각선 방향 `\`과 부대각선 방향 `/`의 두 종류로 나뉜다.
|
|
|
|
|
|
|
|
### 한 행씩 배치하는 전략
|
|
|
|
퀸 수와 체스판의 행 수가 모두 $n$이므로 **각 행에는 퀸을 정확히 하나씩 놓아야 한다**는 사실을 쉽게 도출할 수 있다.
|
|
|
|
따라서 첫 행부터 마지막 행까지 매 행에 퀸 하나씩 놓는 전략을 사용할 수 있다.
|
|
|
|
아래 그림은 4-퀸 문제에서 한 행씩 배치하는 과정이다. 공간 제약 때문에 첫 행의 탐색 가지 중 하나만 펼쳤으며, 열과 대각선 제약을 만족하지 않는 배치는 모두 가지치기했다.
|
|
|
|
|
|
|
|
본질적으로 **행별 배치 전략 자체가 가지치기 역할을 한다**. 같은 행에 여러 퀸이 놓이는 모든 탐색 가지를 피하기 때문이다.
|
|
|
|
### 열과 대각선 가지치기
|
|
|
|
열 제약을 만족하기 위해 길이 $n$의 불리언 배열 `cols`에 각 열의 퀸 존재 여부를 기록할 수 있다. 배치를 결정하기 전에 `cols`로 이미 퀸이 있는 열을 가지치기하고, 백트래킹 중 `cols`의 상태를 동적으로 갱신한다.
|
|
|
|
!!! tip "참고"
|
|
|
|
행렬의 시작점은 왼쪽 위이며, 행 인덱스는 아래로 갈수록, 열 인덱스는 오른쪽으로 갈수록 커진다.
|
|
|
|
대각선 제약은 어떻게 처리할까? 한 칸의 행과 열 인덱스를 $(row, col)$이라고 하자. 주대각선 방향의 대각선 하나를 고르면, 그 위의 모든 칸에서 행 인덱스와 열 인덱스의 차가 같다. **즉, 같은 주대각선 방향 대각선에서는 $row - col$이 일정하다**.
|
|
|
|
따라서 두 칸이 $row_1 - col_1 = row_2 - col_2$를 만족하면 반드시 같은 주대각선 방향 대각선에 있다. 이 규칙을 이용하여 아래 그림의 배열 `diags1`에 각 대각선의 퀸 존재 여부를 기록할 수 있다.
|
|
|
|
마찬가지로 **같은 부대각선 방향 대각선의 모든 칸에서는 $row + col$이 일정하다**. 배열 `diags2`를 이용하여 이 방향의 제약도 처리할 수 있다.
|
|
|
|
|
|
|
|
### 코드 구현
|
|
|
|
$n$ 차 정방행렬에서 $row - col$의 범위는 $[-n + 1, n - 1]$, $row + col$의 범위는 $[0, 2n - 2]$이다. 따라서 두 방향의 대각선 수는 각각 $2n - 1$ 개이며, 배열 `diags1`과 `diags2`의 길이도 모두 $2n - 1$이다.
|
|
|
|
```src
|
|
[file]{n_queens}-[class]{}-[func]{n_queens}
|
|
```
|
|
|
|
행별로 $n$ 번 배치할 때 열 제약을 고려하면 첫 행부터 마지막 행까지 선택지 수가 $n$, $n-1$, $\dots$, $2$, $1$이므로 $O(n!)$ 시간이 걸린다. 해를 기록할 때 행렬 `state`를 복사하여 `res`에 추가해야 하며, 복사에는 $O(n^2)$ 시간이 든다. 따라서 **전체 시간 복잡도는 $O(n! \cdot n^2)$이다**. 실제로는 대각선 제약에 따른 가지치기도 탐색 공간을 크게 줄이므로 위 복잡도보다 탐색 효율이 좋은 경우가 많다.
|
|
|
|
배열 `state`는 $O(n^2)$ 공간을, `cols`, `diags1`, `diags2`는 각각 $O(n)$ 공간을 사용한다. 최대 재귀 깊이가 $n$이므로 스택 프레임 공간은 $O(n)$이다. 따라서 **공간 복잡도는 $O(n^2)$이다**.
|