[BOJ, Python] 9663 - N-Queen ( with Backtracking )

9663번: N-Queen

퇴각 검색 알고리즘을 다룰 때 대표적으로 등장하는 문제다. 2차원 배열이 아닌 인덱스를 행, 요소를 열로 사용하는 1차원 배열을 활용하고, PyPy3로 제출해야만 시간초과 없이 AC를 받을 수 있다.

n = int(input())

# 체스판, 0은 아직 놓이지 않음을 의미
map = [0] * n
ans = 0

# 퀸을 놓을 수 있는지 판단하는 함수
def is_satisfy(x):
    for i in range(x):
    
    	# 같은 열에 놓였는지, 대각선에 놓였는지(-> 절댓값으로 판단, 왼쪽 위, 오른쪽 위)
        if map[i] == map[x] or abs(x - i) == abs(map[x] - map[i]):
            return False
    return True

def n_queens(x):
    global ans
    
	# 마지막 행까지 도달하면 경우의 수 + 1, 함수 종료
    if x == n:
        ans += 1
        return
	
    # 퀸을 놓고 해당 퀸의 위치 만족스러운지 확인 후
    # 다음 행으로 넘어감
    for i in range(n):
        map[x] = i
        if is_satisfy(x):
            n_queens(x+1)

n_queens(0)
print(ans)