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

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

코딩테스트 연습 - N-Queen

 

풀이

1. queen 배열

- ex) queen[1] = 2 -> 1행 2열에 퀸 배치

2. check 함수

- 퀸이 놓일 수 있는지 행, 열, 대각선 확인

- abs(x-i) == abs(queen[x] - queen[i]) : 대각선 방향 확인

- ex) [2, 3]의 대각선 방향 = [1, 2], [0, 1], [1, 4] / [2, 2]의 대각선 방향 = [1, 1], [0, 0], [3, 3] -> 규칙을 이용해서 식 구하기

 

 

=> 0행에 0~n-1열까지 순서대로 퀸을 놓으면서 경우의 수를 찾는다. dfs로 풀면서 안되는 경우에 해당하면 이전 단계로 돌아가는(가지치기) 백트래킹으로 해결할 수 있다.

 

def n_queen(n, x, queen):
    result = 0
    
    if x == n:
        return 1
    
    for i in range(n):
        queen[x] = i
        
        if check(x, queen):
            result += n_queen(n, x+1, queen)

    return result

def check(x, queen):
    for i in range(x):
        if queen[x] == queen[i] or abs(x-i) == abs(queen[x] - queen[i]):
            return False
    return True
    
def solution(n):
    queen = [0] * n
    answer = n_queen(n, 0, queen)
    
    return answer