[프로그래머스] N-Queen

 

문제 설명

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

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

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

제한 사항

-퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.

-n은 12이하의 자연수 입니다.

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

접근법

하나의 배열 col을 생성한 뒤, 하나씩 채워갑니다. col[0]은 0번째에 Q가 있는 인덱스, col[1]은 1번째에 Q가 있는 인덱스를 뜻합니다. nqueen부분에서는 col의 n번째에 각각 인덱스를 하나씩 채워주는 역할을 합니다. 이때 check에서 검사를 한 뒤, 그 자리에 올수 있다면 n+1자리를 검색해 봅니다. 이렇게 계속 하다보면, col의 길이와 n이 같아지는 시점에 count를 더해주면 됩니다.(n이 col의 길이만큼 왔다는 것은, check를 모두 통과했기 때문입니다.)

​

나의 코드

count = 0
def check(col,n):
    for i in range(n):
        if (col[n] in col[:n]) or (abs(col[n]-col[i]) == abs(n-i)): return False
    return True

def nqueen(col,n):
    global count
    if len(col) == n: 
        count += 1
    else:
        for i in range(len(col)):
            col[n] = i
            if check(col,n):
                nqueen(col,n+1)

def solution(n):
    col = [0]*n
    nqueen(col,0)
    return count