[백준] 9663: N-Queen (python/파이썬)

분류

백트래킹, 브루트포스 알고리즘

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

이 문제는 백트래킹 기법을 이용해 푸는 문제이다. 프로미싱 함수를 돌면서 해당 값이 유망한지를 판단하여 조건문을 계속 돌아줘야한다.
마지막 depth까지 도달할 경우에 정답임으로 result 값을 올려주는 것으로 몇개의 정답이 나올지 측정해주자.

n = int(input())
# 행에는 한개 이상의 퀸이 있을 수 없기에 배제하고 열로만 문제를 푼다.
# 입력 받은 N 만큼 0으로된 열을 만들어준다.
col = [0] * n
result = 0

def n_queens(i):
    # n은 dfs의 depth라고 생각하면 된다. 마지막 깊이에 도달했을 때 답을 찾은것이라고 판단할 수 있다.
    global result
    if (i == n):
        # print(col[1:n+1])
        result += 1
    else:
        for j in range(n):
            col[i] = j
            # 프로미싱 함수로 통해 해당 값들이 유망하다 판단되면 아래와 같은 조건들을 실행한다.
            if promising(i):
                n_queens(i + 1)


def promising(x):
    for i in range(x):
        # 같은 열에 있거나 대각선에 있으면 = False
        # 대각선은 y축의 차이 == x축의 차이가 같을때 같은 대각선이다
        if (col[x] == col[i] or abs(col[x] - col[i]) == (x - i)):
            return False
    return True


n_queens(0)

print(result)