백트래킹_PRO#12952 : N-Queen

 

문제 설명

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

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

 

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

제한사항

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

---

 

 

백트래킹은 n이 작을 때(해당 문제: n <= 12) or 어쩔 수 없이 모든 경우의 수를 구해야 할 때 사용한다.

=> 백트래킹은 재귀 구조를 사용한다.

 

def search(queen, row):
    n = len(queen)
    count = 0
    
    if n == row: # 재귀함수 종료
        return 1
    
    for col in range(n):
        queen[row] = col  # (row, col)에 퀸 배치
        
        if check(queen, row):
            count += search(queen, row + 1) # 다음 열로 넘어감
    
    return count
    

def check(queen, row):
    for i in range(row):
        # 하나의 행에서 같은 열에 위치 or 대각선에 위치할 경우 False
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == (row-i):
            return False
    return True


def solution(n):
    return search([0] * n, 0)