[BOJ/백준] 9663번 N-Queen (Python/파이썬)

https://www.acmicpc.net/problem/9663

9663번: N-Queen

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	71288	34721	22727	47.810%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

예제 입력 1

8

예제 출력 1 

92

 

---

풀이

 

백 트래킹 (backtracking)에 대해서 간단하게 정리하면 다음과 같습니다.

• 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름
• 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법
• 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현각 후보군을 DFS 방식으로 확인
  상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
• Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
• Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
• 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)

Promising

문제를 살펴보면 제약 조건을 다음과 같이 설정할 수 있습니다.

1. 서로 다른 퀸들은 다른 열과 행에 존재한다.
2. 서로 다른 퀸들은 체스판 상 대각선 상에 존재하면 안된다.

해당 제약조건을 가지고 가지치기를 진행하면 됩니다.

Pruning

1. 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치, 즉 다음 퀸을 놓을 수 있는 위치를 찾아서 배치한다.
2. 이는, 행을 차례대로 DFS 방식으로 접근하여 제약조건을 확인하고, 만약 해당 경우가 제약 조건에 맞지 않는다면 더 이상 탐색을 진행하지 않고 backtrack 한다.

예를 들어서 4x4 체스판에 첫 행과 두 번째 열에 첫 번째 퀸을 배치했다고 가정합시다. 편의를 위해 (0,1)로 표현하겠습니다.
다음 행의 경우의 수는 (1,0) (1,1) (1,2) (1,3)으로 총 4개입니다.
이 중 진행이 가능한 경우는 위에서 설정한 제약조건에 의해서 (1,3) 밖에 없습니다.
이를 트리로 표현하자면, 부모 노드 (0,1)에서 뻗어 나간 (1,0) (1,1) (1,2) (1,3) 4가지 자식 노드들 중에서 (1,3)을 제외한 나머지 3개의 자식 노드에 대해서 가지치기를 진행합니다.
이제는 (1,3)에 대해서 (2,0) (2,1) (2,2) (2,3)을 검사하여 가지치기를 결정합니다.

제약 조건은 어떻게 구현할까요? 다음 두 가지를 검사하면 됩니다.

1. 수직 체크 : 현재 하나의 row에 대해서 검사를 진행하므로, 이전 퀸과 같은 column인지 검사합니다.
2. 대각선 체크 : 체스판 상에서 같은 대각선 상에 위치하기 위해서는 x좌표의 증가량과 y좌표의 증가량이 동일해야 합니다. 

따라서 이를 코드로 표현하면 다음과 같습니다.

if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row:
            return False

가지치기를 어떻게 구현할까요? 거꾸로 생각하면, 가지치기를 당하지 않은 노드들에 대해서만 DFS를 진행하면 됩니다.
즉, 후보군들을 순차적으로 돌면서 해당 위치에 퀸을 놓아도 되는지 검사하여 통과되는 경우에만 퀸을 배치합니다.

위 내용을 토대로 전체 코드를 작성하면 다음과 같습니다.

from sys import stdin
input = stdin.readline
n = int(input())
cnt = 0

def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):  # abs- 절댓값 함수
        # 수직 체크 or 대각선 체크
        if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row:
            return False
    return True


def DFS(N, current_row, current_candidate):
    global cnt
    if current_row == N:  # 여기까지 호출됐다는 것은 퀸의 배치가 완료된 것.
        cnt += 1
        return

    for candidate_col in range(N):
        if is_available(current_candidate, candidate_col):
            current_candidate.append(candidate_col)
            DFS(N, current_row + 1, current_candidate)
            current_candidate.pop()  # 백트래킹


def solve_n_queens(N):
    DFS(N, 0, [])
    print(cnt)
    return

solve_n_queens(n)

 

backtracking 문제를 푸실 때는 이번 포스팅에서 정리한 흐름을 따라가면서 제약 조건을 설정하고 가지치기를 적절히 수행하면 됩니다.

DFS에서는

1. 가장 먼저 탐색의 종료 조건을 확인하고, 
2. 반복문 내에서 제약 조건을 검사하여 가지 치기를 진행합니다.
3. 모든 경우의 수를 검토하기 위해서 위 코드와 같이 각 후보군에 대해서
   append()
   DFS(depth + 1)
   pop()
   형식으로 백트래킹을 구현합니다.

 

또 다른 풀이법이 있어 남겨드리고 포스팅 마치겠습니다!

n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)


def solve(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False  # Back_Tracking


solve(0)
print(ans)