N-Queens II
퀸은 아무리 멀리 떨어져 있어도 자신의 행, 열, 양쪽 대각선에 있는 모든 칸을 공격합니다. 정수 n이 주어졌을 때, 서로 공격하지 않도록 n × n 체스판에 n개의 퀸을 배치하는 방법의 수를 반환하세요.
한 칸이라도 다른 체스판은 각각 별개의 경우로 셉니다. 거울상도 포함됩니다.
함수
- ninteger
- 보드의 크기와 퀸의 수
- 반환값integer
- 서로 공격하지 않도록 퀸을 배치하는 방법의 수
제약 조건
1 ≤ n ≤ 12-
n = 12의 답은 14,200이므로 32비트 정수에 들어갑니다.
예제
- 입력
- n = 4
- 출력
- 2
- 설명
- 각 행의 퀸이 놓인 열을 위에서 아래로 적으면, 보드는
1, 3, 0, 2와2, 0, 3, 1입니다. 서로 거울상인 두 가지로 셉니다. 다른 모든 배치는 두 퀸이 같은 열이나 대각선에 놓이게 합니다.
- 입력
- n = 3
- 출력
- 0
- 설명
- 맨 위 모서리에 퀸을 놓으면 가운데 행에 안전한 칸이 하나 남고, 그러면 맨 아래 행에는 안전한 칸이 하나도 없습니다. 맨 위 가운데에 퀸을 놓으면 가운데 행 전체를 공격합니다.
후속 질문
보드를 회전하거나 뒤집어도 서로 다른 상태로 남는 보드만 셀 수 있나요? n = 8일 때, 92개의 보드는 이러한 12개의 그룹으로 나뉩니다.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
같은 행에 있는 두 퀸은 서로 공격하므로, 각 행에는 정확히 하나의 퀸만 놓입니다. 이를 알고 나면 무엇을 선택하면 될까요?
보드를 위에서부터 한 번에 한 행씩 채우세요. 새 퀸이 공격받는 즉시 그 부분 보드를 포기하세요. 아래에 무엇을 더 놓더라도 문제를 해결할 수 없기 때문입니다. 보드 전체를 살펴보지 않고도 칸을 확인하려면, 이미 퀸이 있는 열과 대각선을 기억하세요. 한쪽 대각선 방향에서는 모든 칸의
row + col값이 같고, 다른 쪽에서는row - col값이 같습니다.place(row)를 작성하세요. 이 함수는 여기서 완성할 수 있는 보드의 개수를 반환합니다.row == n일 때는 1을 반환합니다. 그렇지 않으면 열,row + c대각선,row - c대각선이 모두 비어 있는 모든 열c를 시도합니다. 세 곳을 표시하고, 누적 합계에place(row + 1)을 더한 다음 표시를 해제합니다. 정답은place(0)입니다.
풀이
같은 행에 있는 두 퀸은 항상 서로를 공격하므로, 보드는 각 행마다 한 열씩 선택하는 방식으로 표현됩니다. 가능한 목록은 n^n개이며, n = 12일 때 약 8.9 × 10^12개입니다. 대신 행마다 보드를 구성하고, 퀸이 공격을 받는 즉시 부분 보드를 버리세요. 이미 차지된 열과 대각선을 표시해 두면 한 칸을 검사하는 데 조회 세 번이면 됩니다.
각 행에 퀸을 하나씩 두는 모든 배치를 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
배치를 cols 리스트로 작성합니다. 각 행의 퀸이 놓인 열을 나타내며, 주행 기록계처럼 모든 n^n개의 리스트를 차례로 확인합니다. i < j인 행의 퀸들은 cols[i] == cols[j] 또는 |cols[i] - cols[j]| == j - i일 때 서로 공격합니다. 대각선으로 한 행 이동할 때마다 열이 하나씩 이동하기 때문입니다. 각 리스트를 한 번씩 확인하므로 빠뜨리거나 두 번 세는 배치는 없습니다.
어떤 경우에도 일찍 멈추지 않습니다. 처음 두 행에서 충돌하더라도 n^(n-2)개의 리스트가 남습니다. n = 8이면 92개의 보드에 대해 16,777,216개의 리스트를 확인해야 하며, n = 12이면 8.9 × 10^12개로, 각각을 나노초마다 확인해도 약 2.5시간이 걸립니다.
알고리즘
cols를 모두 0으로 시작합니다.- 행 쌍
i < j중cols[i] == cols[j]또는|cols[i] - cols[j]| == j - i인 쌍이 없으면 개수에 1을 더합니다. - 주행 기록계처럼 진행합니다. 마지막 행부터 거슬러 올라가며
n-1인 각 항목을 0으로 재설정한 다음,n-1보다 작은 첫 번째 항목에 1을 더합니다. - 모든 항목이
n-1이었으면 멈추고 개수를 반환합니다.
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1열과 대각선 집합을 사용한 백트래킹
핵심 아이디어
퀸을 행별로 배치하고, 하나를 놓을 때마다 검사합니다. 아래 행을 채워도 공격받는 퀸을 구할 수 없으므로 해당 칸은 건너뜁니다. 안전한 퀸을 놓으면 다음 행으로 재귀 호출하고, 호출이 반환되면 퀸을 제거합니다. 행 n에 도달하면 보드 하나로 계산합니다.
칸 (row, c)을 공격할 수 있는 선은 세 개뿐입니다. 열, / 대각선(여기서는 row + c가 일정함), 그리고 \ 대각선(여기서는 row - c가 일정함)입니다. 0부터 인덱싱하려면 n-1을 더합니다. 플래그 배열 cols, diag, anti를 사용하면 안전성 검사를 세 번의 조회로 처리할 수 있습니다. 각 선에는 퀸을 최대 하나만 놓을 수 있으므로, 반환할 때 플래그를 해제하면 배열이 정확히 원래 상태로 복원됩니다.
행 k에는 최대 n - k개의 열이 있으므로, 탐색의 상한은 O(n!)이며 공간 복잡도는 O(n)입니다.
알고리즘
- 크기
n의 플래그 배열cols와 크기2n-1의diag및anti를 만들고, 모두 꺼 둡니다. place(row):row == n이면 1을 반환합니다.- 각 열
c에 대해,cols[c],diag[row + c]또는anti[row - c + n - 1]가 켜져 있으면 해당 열을 건너뜁니다. - 그렇지 않으면 세 플래그를 켜고, 총합에
place(row + 1)을 더한 다음 플래그를 끕니다. - 총합을 반환합니다. 정답은
place(0)입니다.
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)비트마스크를 이용한 백트래킹
핵심 아이디어
깃발 검색은 여전히 각 행의 n개 열을 모두 검사합니다. 비트마스크는 비어 있는 칸으로 바로 이동합니다. 비트 c는 채우고 있는 행의 열 c를 나타냅니다. cols에는 이미 차지한 열이 들어 있고, left와 right에는 각 대각선에서 공격받는 칸이 들어 있습니다. 그러면 full이 하위 n비트일 때 free = ~(cols | left | right) & full이 되고, free & -free는 가장 낮은 위치의 비어 있는 칸입니다. 한 행 아래로 내려가면 열은 계속 차지된 상태이고 각 대각선의 공격 범위는 한 열씩 이동합니다.
n = 4이고 첫 번째 퀸이 bit = 0010에 있을 때, 1행에는 free = 1000이 주어집니다. 다른 칸을 검사하지 않고 열 3을 찾습니다. n = 12에서는 10,103,868개의 칸을 검사하는 대신 루프를 856,188회 수행합니다. R 코드는 재귀하는 대신 부분 보드의 행 전체를 한 번에 확장합니다.
알고리즘
full = (1 << n) - 1로 설정합니다.count(cols, left, right):cols == full이면 1을 반환합니다.free = ~(cols | left | right) & full을 계산합니다.free가 0이 아닌 동안bit = free & -free를 가져와free에서 제거하고,count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)을 전체 합계에 더합니다.- 전체 합계를 반환합니다. 답은
count(0, 0, 0)입니다.
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
함정과 경계 사례
n-1을 더하지 않고row - c로anti를 인덱싱하는 것. Java에서는 예외가 발생하고, C에서는 배열 바깥을 읽으며, Python의anti[-2]는 조용히 다른 대각선의 플래그를 읽습니다.- 대각선 배열의 크기를
2n-1이 아니라n으로 지정하는 것.row + c는2n-2까지 도달합니다. - 재귀 호출 후 플래그를 지우지 않는 것. 이후 분기에서 이미 사라진 퀸이 있는 것으로 간주하여 개수가 줄어듭니다.
free에서& full을 빼먹는 것.~x는 열n-1위쪽의 비트를 설정하므로, 반복문이 보드 밖의 칸을 선택합니다. Python이나 Ruby에서는free가 음수가 되어 반복문이 끝나지 않습니다.
자주 묻는 질문3
N-Queens II의 시간 복잡도는 얼마인가요?
백트래킹의 상한은 O(n!)입니다. 첫 번째 행에는 n개의 선택지가 있고, 다음 행에는 최대 n-1개가 있으며, 이런 식으로 이어집니다. 가지치기를 하면 실제 작업량은 훨씬 줄어들어 n = 12일 때 부분 보드가 856,189개입니다. 공간 복잡도는 O(n)입니다.
N-Queens와 N-Queens II의 차이점은 무엇인가요?
N-Queens는 텍스트 행으로 그린 모든 보드를 반환하고, N-Queens II는 보드의 개수만 반환합니다. 탐색 방식은 같지만, 개수만 세면 보드를 저장하지 않으므로 비트마스크 버전에 적합합니다.
대칭성을 활용해 N-Queens II의 속도를 높일 수 있을까요?
보드를 좌우로 뒤집으면 또 다른 유효한 보드가 되므로, 첫 번째 퀸이 0부터 n/2 - 1까지의 열에 있는 보드의 수를 세고 두 배로 합니다. n이 홀수이면 첫 번째 퀸이 가운데 열에 있는 보드의 수를 한 번 더합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def totalNQueens(n):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
n = 4
예상 출력
2