가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
입출력 예
n | result |
---|---|
4 | 2 |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
첫번째 행에 차례대로 퀸을 놓고 퀸을 놓을 때마다 갈수 있는 다음 자리를 저장하며 탐색한다.
def solution(n):
answer = 0
available = set()
for i in range(1,n):
for j in range(n):
available.add((i,j))
for i in range(n):
stack = []
next,path = get_path(set()|available,0,i)
stack.append([(0,i),next,path])
while stack:
if len(stack[-1][1]) != 0:
next_ = stack[-1][1].pop()
next_next,path = get_path(stack[-1][2],next_[0],next_[1])
stack.append([next_,next_next,path])
else:
if stack[-1][0][0] == n-1:
answer += 1
stack.pop()
return answer
def get_path(s,i,j):
ns = set()
ns = ns | s
next_ = set()
for r,c in s:
if i+j == r+c or i-j == r-c or i == r or j == c:
ns.remove((r,c))
elif r == i+1:
next_.add((r,c))
return (next_,ns)