[AlgorithmSolving][backtracking] JUNGOL_1889: N Queen
1. 문제 내용
-
문제:
체스에서 queen은 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다.
즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.
N×N 크기의 정방형 체스판이 주어졌다. 우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다. 그렇다면 queen들을 어떻게 배치해야만 할까?
가능한 모든 경우의 개수를 출력한다.
-
입력:
queen의 수 N(1≤N≤13)을 입력 받는다.
-
출력:
$N \times N$ 의 체스판에서 N개의 queen들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법의 수를 출력한다.
2. 문제 유형 파악
이 문제는 알고리즘 분야에서 백트래킹과 상태 공간 트리(State Space Tree) 탐색을 설명할 때 가장 먼저 등장한느 교과서적인 문제인 ‘N-Queen’입니다.
- 알고리즘 분류: DFS를 활용한 백트래킹
- 시간 복잡도 평가: NxN 체스판에 N개의 퀸을 놓는 모든 경우의 수는 $\binom{N^2}{N}$으로 천문학적인 숫자입니다. 하지만 ‘각 행과 열에는 단 하나의 퀸만 존재할 수 있다는’ 조건을 적용하면 $N!$로 줄어들며, 여기서 유망성 검사(Promising)를 통한 가지치기(Pruning)를 적용하면 탐색 공간을 극적으로 압축할 수 있습니다. 문제의 제한 조건이 $N \le 13$ 이므로, 최적화된 백트래킹을 사용하면 시간 초과 없이 안전하게 통과할 수 있습니다.
3. 문제를 풀기 위한 핵심 아이디어
이 문제를 효율적으로 해결하기 위한 핵심은 “2차원 체스판을 1차원 배열로 압축하고, 수학적 규칙을 통해 대각선 충돌 여부를 빠르게 판별하는 것”입니다.
- 1차원 배열로의 차원 축소(공간 최적화)
보통 N x N 체스판이라고 하면 2차원 배열을 떠올리기 쉽습니다. 하지만 퀸은 같은 행(Row)에 두 개 이상 놓일 수 없으므로, 굳이 2차원 배열을 쓸 필요가 없습니다.
- 크기가 N인 1차원 배열 row를 선언합니다.
- `row[i] = j`의 의미: i번째 행의 j번째 열에 퀸을 배치했다는 뜻입니다.
- 이러한 접근법은 메모리 사용량을 $O(N^2)$에서 $O(N)$으로 줄여줄 뿐만 아니라, '같은 행에 퀸이 존재하는가?'라는 검사 자체를 생략할 수 있게 해주는 아주 우아한 최적화 기법입니다.
- 유망성 검사(가지치기 규칙)
현재 i번째 행에 퀸을 놓기 위해 열 j를 선택했다고 가정해 봅시다. 이 자리가 안전한지(Promising) 확인 하려면, 이전에 배치한 0부터 i-1번째 행까지의 퀸들과 비교해야 합니다. (과거의 퀸들을 k라고 하겠습니다.)
- 같은 열(Column)에 있는지 검사:
- `row[i] = row[k]` 라면 같은 열에 퀸이 존재하므로 배치할 수 없습니다.
- 같은 대각선(Diagonal)에 있는지 검사
- 체스판에서 두 좌표가 같은 대각선상에 있다는 것은, 두 좌표의 가로 거리(열의 차이)와 세로 거리(행의 차이)가 같다는 수학적 의미를 가집니다.
- 즉, `abs(row[i] - row[k]) == abs(i-k)`라면 같은 대각선상에 있으므로 배치할 수 없습니다.
-
DFS를 이용한 완전 탐색과 백트래킹
- 0번째 행부터 시작하여 퀸을 하나씩 놓습니다. (DFS(row=0))
- goekd goddptj 0부터 N-1 까지의 열을 순회하며 앞서 도출한 유망성 검사를 통과하는 열에만 퀸을 배치합니다.
- 안전한 자리라면 퀸을 놓고 다음 행으로 넘어갑니다. (DFS(row+1))
- 만약 현재 행에서 더 이상 퀸을 놓을 수 있는 자리가 없다면, 즉시 함수를 종료하고 이전 행으로 돌아가(backtrack) 다른 열을 탐색합니다.
- 이 과정을 반복하여 퀸을 무사히 마지막 행까지 배치했다면 정답 카운트를 1 증가시킵니다.
4. 코드
다음은 해당 문제를 푼 코드입니다.
import sys
def solve():
input = sys.stdin.readline
n = int(input())
cols_check = [False] * n
right_diagonal_check = [False] * (2*n-1)
left_diagonal_check = [False] * (2*n-1)
answer = 0
def backtrack(row):
nonlocal answer
if row == n:
answer+=1
return
for col in range(n):
left_diagonal = row+col
right_diagonal = row-col + (n-1)
if not cols_check[col] and not right_diagonal_check[right_diagonal] and not left_diagonal_check[left_diagonal]:
cols_check[col] = True
right_diagonal_check[right_diagonal] = True
left_diagonal_check[left_diagonal] = True
backtrack(row+1)
cols_check[col] = False
right_diagonal_check[right_diagonal] = False
left_diagonal_check[left_diagonal] = False
backtrack(0)
print(answer)
solve()
5. 복기 및 최적화
5.1 코드 복기
-
대각선 체크 배열의 길이가 (2n-1)인 이유
N-Queen 문제를 1차원 배열로 최적화할 때, 처음 접하는 분들이 가장 헷갈려 하는 부분이 바로 대각선 배열의 크기입니다. “어떤 위치에 퀸을 놓았을 때 뻗어나가는 대각선 칸이 최대 N개니까 배열의 크기도 N개인가?”라고 접근하면 헤메게 됩니다.
이 배열의 크기를 이해하기 위한 핵심은 체스판을 칸이 아니라 선(Line)으로 바라보는 발상의 전환에 있습니다.
-
대각선은 뻗어나가는 칸이 아니라 이미 고정된 차선이다
우리가 만든 대각선 체크 배열은 퀸을 놓을 때마다 퀸이 공격할 수 있는 칸을 일일이 쫓아가며 색칠하기 위해 만든 것이 아닙니다. 체스판 전체에는 처음부터 우상단->좌하단(/) 방향의 차선들과, 좌상단->우하단() 방향의 차선들이 그어져 있습니다. 특정 좌표에 퀸을 놓는다는 것은 곧 “나는 지금
/방향의 X번 차선과\방향의 Y번 차선을 통째로 점유하겠다”라고 선언하는 것과 같습니다. -
체스판에 존재하는 고유한 대각선 세어보기
그렇다면 NxN 체스판 전체에 고유한
/방향 대각선 차선은 총 몇 개가 존재하는지 직접 세어보도록 하겠습니다. 아래 8x8 체스판이 있다고 가정하겠습니다. 숫자는 좌표값을 의미합니다.(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7) (1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (3, 7) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) (4, 7) (5, 0) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) (5, 7) (6, 0) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) (6, 7) (7, 0) (7, 1) (7, 2) (7, 3) (7, 4) (7, 5) (7, 6) (7, 7)-
1번째 선 (합 0): (0, 0)
-
2번째 선 (합 1): (0, 1), (1, 0)
-
3번째 선 (합 2): (0, 2), (1, 1), (2, 0)
-
4번째 선 (합 3): (0, 3), (1, 2), (2, 1), (3, 0)
-
5번째 선 (합 4): (0, 4), (1, 3), (2, 2), (3, 1), (4, 0)
-
6번째 선 (합 5): (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)
-
7번째 선 (합 6): (0, 6), (1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 0)
-
8번째 선 (합 7 - 가장 긴 정중앙 대각선): (0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)
-
9번째 선 (합 8): (1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1)
-
10번째 선 (합 9): (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2)
-
11번째 선 (합 10): (3, 7), (4, 6), (5, 5), (6, 4), (7, 3)
-
12번째 선 (합 11): (4, 7), (5, 6), (6, 5), (7, 4)
-
13번째 선 (합 12): (5, 7), (6, 6), (7, 5)
-
14번째 선 (합 13): (6, 7), (7, 6)
-
15번째 선 (합 14): (7, 7)
개수를 세어보면 2*8-1인 15개가 됩니다. 그렇다면 반대로 좌상단->우하단의 개수도 15개가 될 것입니다.
-
-
-
대각선 인덱스 계산 방식
체스판의 좌표를 통해 왜 각각 row+col과 row-col+(n-1)이라는 공식이 도출되는지 8x8 배열을 통해 증명해 보도록 하겠습니다.
-
우상단 -> 좌하단 방향 대각선 (
/모양) row+col이 방향의 대각선상에 놓인 좌표들의 공통점은 ‘행과 열의 인덱스를 더한 값이 항상 일정하다’는 것입니다.
- 합이 2인 대각선 : (0, 2), (1, 1), (2, 0) $\rightarrow$ $0+2 = 1+1 = 2+0 = 2$
- 합이 7인 대각선 : (0, 7), (1, 6), (2, 5), …, (7, 0) $\rightarrow$ 모두 더하면 7
이처럼 row+col의 값은 최소 0부터 최대 (N-1) + (N-1) = 2N-2까지 나옵니다. 총 2N-1개의 고유한 값이 나오며, 이 합계의 값을 그대로 배열의 인덱스로 사용하여 해당 대각선의 점유 여부를 $O(1)$로 확인할 수 있습니다.
-
좌상단 -> 우하단 방향 대각선(
\모양): row - col + (N-1)이 방향의 대각선상에 놓인 좌표들의 공통점은 ‘행에서 열의 인덱스를 뺀 값이 항상 일정하다’는 것입니다.
- 차이가 0인 대각선 (정중앙): (0, 0), (1, 1), (2, 2), …, (7, 7) $\rightarrow$ $0-0 = 1-1 = 7-7 = 0$
- 차이가 -1인 대각선 (중앙 우측): (0, 1), (1, 2), (2, 3), …, (6, 7) $\rightarrow$ $0-1 = 1-2 = 6-7 = -1$
문제는 이 뺄셈의 결과로 음수가 나올 수 있다는 점입니다. 뺄셈 값은 최소 $0 - (N-1) = -(N-1)$부터 최대 $(N-1) - 0 = N-1$까지 나옵니다.
파이썬을 비롯한 프로그래밍 언어에서 음수를 배열의 인덱스로 바로 사용하면 오류가 발생하거나 의도치 않은 맨 뒤쪽 원소에 접근하게 됩니다. 따라서 가장 작은 음수인 $-(N-1)$을 $0$으로 만들어 주기 위해 모든 결과값에 일괄적으로 $(N-1)$을 더해주는 보정 작업을 거칩니다. 그러므로 (N-1) 값을 row-col 값에 더해주는 것입니다.
-
Comments