문제 출처

문제 요구사항 정리

1. nxn 체스판에 n개의 퀸이 있을 때 서로 잡지 못하는 포지션의 개수는?

문제 이해

해당 문제는 유명한 퀸문제이다.

이 문제를 풀기 위해 백트래킹을 이해해야한다.

알고리즘 참고 링크

백트래킹은 간단히 얘기해서 어떠한 해를 고를 경우 해당 해가 틀렸을 때 뒤로 돌아가서 다시 맞는 해를 찾아내는 것이다.

먼저 해당 체스판에서 퀸을 놓는 것부터 생각해보자.

문제에서 주어진 것처럼 퀸을 놓을 때 조건은 서로 잡지 못할 경우 뿐이다.

이 조건을 정리하면 아래와 같다.

1. 퀸끼리 같은 행(열)에 있을 경우
2. 퀸끼리 같은 대각선에 있을 경우

또한, 퀸은 열(행)에 최대 하나밖에 있을 수 있다. 그럼으로 위의 내용을 정리했을 때 우리는 아래와 같은 메서드를 작성해야 한다.

1. 체스판에서 퀸들이 서로 잡지 못하는 것을 체크하는 메서드
2. 퀸을 해당 행에 두는 메서드
   2-0. 해당 행의 퀸을 하나씩 둠
   2-1. 1번 메서드를 통해 조건이 성립될 경우 다음 열(행)로 이동
   2-2. 1번 메서드를 통해 조건이 성립되지 않을 경우 해당 행의 다른 열로 둠

이를 코드로 정리하면 아래와 같다.

아래의 코드는 1차원 배열로 두었는데, 각각의 인덱스는 열이고 배열값은 행이 될 것이다.

예를 들어, [1,2,3,4]인 경우 0번째 행에는 퀸이 1번째 열에 있다고 가정한 것이다.

import sys


def checkDuplecate(x):
    for i in range(x):
        if board[i] == board[x] or abs(board[x] - board[i]) == abs(x - i):
            return True
    return False


def backtracking(x):
    global ans
    if x == n:
        ans += 1
        return
    for y in range(n):
        board[x] = y
        if not checkDuplecate(x):
            backtracking(x + 1)


def solution():
    global n, board, ans
    input = sys.stdin.readline
    n = int(input())
    ans = 0
    board = [0 for _ in range(n)]

    backtracking(0)
    print(ans)


solution()