(Python) - 프로그래머스 : N-queen

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

• 해설 :

백트래킹의 대표문제인 n-queen 문제이다. n*n 체스판에 n개의 퀸을 놓을 수 있는 방법의 수를 찾는 문제이다. 

 

 

 

• 풀이 :

백트래킹은 pruning이 중요하다고 배웠다. 재귀로 모든 경우를 탐색하지만 더 탐색해도 의미가 없는 경우 (절대 답이 될 수 없는 경우) 에 대한 조건으로 재귀를 종료해주어야 한다. n-queen의 경우 세로, 또는 대각선에 퀸이 놓여져있는 경우를 pruning조건으로 선택하면 된다. 

 

 

 

 

def dfs(queen, row, n):
    count = 0
    if n == row:
        return 1
    for col in range(n):
        queen[row] = col
        for i in range(row):
            if queen[i] == queen[row]:
                break
            if abs(queen[i]-queen[row]) == row - i:
                break
        else:
            count += dfs(queen, row + 1, n)
    return count
def solution(n):
    return dfs([0]*n, 0, n)