[백준/파이썬/브루트포스] 9663번 N-Queen 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제

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

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

 

입력

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

 

출력

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

 

정답

def dfs(depth):
    global count
    if depth == n:
        count += 1
        return

    for i in range(n):
        if visited[i]==0:
            graph[depth] = i
            check=True
            for j in range(depth):
                if abs(graph[depth]-graph[j])==abs(depth-j):
                    check=False
                    break
            if check:
                visited[i] = 1
                dfs(depth+1)
                visited[i] = 0

n = int(input())
graph = [0]*n
visited = [0]*n
count=0
dfs(0)
print(count)

위의 코드는 Pypy로 제출해야합니다.

 

야매 정답

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])