Lv3 N-Queen

문제

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예

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)