[백준/알고리즘] #9663:N-Queen[파이썬(python)/백트래킹]

https://www.acmicpc.net/problem/9663

9663번: N-Queen

처음에 문제 힌트에 퀸 노래 있는 거보고 무슨 문제지 대체..? 싶었다 

 

체스의 퀸을 뜻하는 것이었다.

 

N-Queen 이 문제는 백트래킹에서 대표적인 문제라고 한다. 

 

체스판에서 퀸은 중요한 아이로! 가로 세로 대각선 거리제한 없이 쭉 쭉 뻗어 이동할 수 있는 아이입니다.

 

퀸 N개가 서로 공격할 수 없는 경우라 하면

가로 세로 대각선에 퀸이 겹치지 않게 하는 경우겠지요

 

그걸 백트래킹으로 구현해봅니다.

백트래킹은 조건을 걸어 그 조건에 만족하지 않으면 다음 아이로 넘어가서 탐색하는 기법입니다.

 

이 조건을 충족하느냐? Promising? 이라는 용어를 사용하고 

충족하지 않는다면 가지치기, 즉 Pruning을 시행합니다.

 

 

조건체크 (Pruning 작업)

i) 수직체크: cur_col - queen_col = 0 ? 

퀸은 한 행에 한 개씩만 배치 가능함

 

ii) 대각선 체크: abs(queen_col - cur_col) = queen_row - cur_row ?

 

그리고 Promising한 곳이라면 visited으로 체크해줍니다. 

 

#9663_N-queen
n=int(input())
board_row = [0] * n
res=0
visited=[False]*n


def promising_check(cur_col):
    for i in range(cur_col):
        if abs(board_row[cur_col]-board_row[i]) == cur_col-i:
            return False
    return True

def n_queen(cur_col):
    global res
    if cur_col == n:
        res += 1
        return 
    for i in range(n):
        if visited[i]:
            continue
        board_row[cur_col]=i
        if promising_check(cur_col):
            visited[i]=True
            n_queen(cur_col+1)
            visited[i]=False

n_queen(0)            
print(res)