[백준_9663] N-Queen

문제 보기: https://www.acmicpc.net/problem/9663

9663번: N-Queen

문제

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

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

 

입력

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

출력

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

 

새로 사용한 함수

사용했다 제거함

abs(col[i] - col[x]) == x - i:

abs는 절대값을 구하는 함수입니다.

 

풀이 과정

1. 가능 여부를 확인할 때, 상하좌우 대각선을 확인해야 한다.

2. 3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체크한다.

3. N x N 판에서 한 칸의 인덱스를 [X, Y]라 하자. 세로 줄(|)은 각 칸이 [Y]이며, 대각선(/)은 각 칸이 [X+Y]이고, 대각선(\)은 각 칸이 [X-Y+N-1]이다. 아래의 그림은 N이 5일 때의 예시다.

4. solve 함수에서 인자 i는 행(row)이며, for 문의 j는 열(column)을 나타낸다. 즉, 가장 위 행에서 아래 행으로 순서대로 내려가면서, for 문과 if 문을 통해 어떤 열에 놓을지 결정하는 것이다.

 

 

 

코드

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

solve(0)
print(ans)