hello-algo/ko/docs/chapter_backtracking/n_queens_problem.md

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$이다.

[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)$이다.