[백준] 9663번 - N-Queen

📩 출처

문제

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

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

입력

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

출력

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

👉 생각

• 0번째 행의 0번째 열부터 n-1까지 퀸을 하나 놓은다고 가정했을 때 그 바로 아래 가능한 좌표를 찾고 다시 그 정보를 가지고 아래 열들을 찾아가는 완전탐색 방법을 이용하였다.
• 방문 체크를 통해 현재 좌표가 퀸의 자리로 가능한지 알 수 있고 가능하다면 방문 체큰 한 뒤 그 바로 아래 열을 찾아 가도록 했다.

def queen(x):
    global cnt
    if x == n:
        cnt += 1
        return

    for j in range(n):
        if v1[j] == v2[x+j] == v3[x-j] == 0:
            v1[j] = v2[x+j] =v3[x-j] = 1
            queen(x+1)
            v1[j] = v2[x+j] =v3[x-j] = 0

n = int(input())

cnt = 0
v1, v2, v3 = [0] * n, [0]*(2*n), [0]*(2*n)
queen(0)

print(cnt)