[프로그래머스] N- Queen - python

N- Queen

문제 설명

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

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

제한사항

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

풀이

• 각 행의 queen의 위치를 담을 1차원 배열 col을 만든다.
• 0번째 행의 0번째 열부터 일단 넣어보고 가능한지 재귀하며 확인한다.
• 만약 마지막 행까지 퀸을 놓을 수 있으면 조건에 만족하는 방법의 수이므로 1을 리턴한다.
• 총 방법의 수를 리턴한다.

def check(x, y, col):
    for i in range(x):
        if col[i] == y or abs(y - col[i]) == x - i:
            return False
    return True
    
​
def queen(x, n, col):
    if x == n:
        return 1
    cnt = 0
    for y in range(n):
        if check(x, y, col):
            col[x] = y
            cnt += queen(x + 1, n, col)
    
    return cnt
            
            
​
def solution(n):
    col = [0] * n
    return queen(0, n, col)