[백준] 9663번: N-Queen

문제

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

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

입력

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

출력

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

입출력 예제

풀이

1. 변수 초기화

• N은 체스판의 크기를 나타냅니다.
• answer은 해의 개수를 저장합니다.
• check_col, check_diagonal, check_reserve_diagonal은 퀸이 놓여있는 열과 대각선을 체크합니다.

2. solution(N) 함수 호출

• 메인 함수인 solution이 호출되면서 백트래킹 알고리즘을 시작합니다.

3. 백트래킹 시작 (back_tracking 함수)

• row=0과 세 개의 빈 set으로 back_tracking 함수를 처음 호출합니다.

4. 재귀적 탐색

• 각 행(row)에서 가능한 모든 열(col)에 대해 퀸을 놓을 수 있는지 검사합니다.
• 퀸을 놓을 수 있는지 체크하는 조건은 세 가지입니다.
  • 같은 열에 퀸이 없어야 함 (col not in check_col)
  • 같은 대각선에 퀸이 없어야 함 ((row - col) not in check_diagonal)
  • 같은 역대각선에 퀸이 없어야 함 ((row + col) not in check_reserve_diagonal)

5. 조건 만족 시 퀸 놓기

• 모든 조건을 만족한다면, 퀸을 놓고 관련 정보를 업데이트합니다.

6. 다음 행으로 이동

• 퀸을 놓았다면, 다음 행으로 이동하여 같은 과정을 반복합니다.

7. 해 찾기

• 모든 행에 퀸을 놓았다면 하나의 해를 찾았으므로 answer를 1 증가시킵니다.

8.백트래킹 (되돌리기)

• 퀸을 놓을 수 없거나 해를 찾은 후에는 원래의 상태로 되돌립니다. 이를 통해 다른 가능한 해를 찾을 수 있습니다.

9.결과 출력

• 모든 가능한 행과 열을 탐색한 후, answer에 저장된 해의 개수를 출력합니다.

# N은 체스판의 크기입니다. answer는 해의 개수를 저장합니다.
N = int(input())
answer = 0

# 백트래킹 함수를 정의합니다.
def back_tracking(row, check_col, check_diagonal, check_reserve_diagonal):
    global answer  # 전역 변수 answer를 사용합니다.
   
    # 모든 행에 퀸을 놓았으면 하나의 해를 찾은 것입니다.
    if row == N:
        answer += 1  # 해의 개수를 증가시킵니다.
        return
  
    # 각 열에 퀸을 놓아 보면서 유효한지 검사합니다.
    # 대각선과 역대각선을 체크하는 로직:
    # 대각선은 행과 열의 차가 항상 같습니다. (row - col)
    # 역대각선은 행과 열의 합이 항상 같습니다. (row + col)
    # 따라서 대각선과 역대각선에 있는지 체크하기 위해서는 
    # (row - col)과 (row + col) 값을 검사하면 됩니다.
    for col in range(N):
        # 해당 위치에 퀸을 놓을 수 있는지 검사합니다.
        if col not in check_col and (row - col) not in check_diagonal and (row + col) not in check_reserve_diagonal:
           
            # 퀸을 놓을 수 있다면, 관련 정보를 업데이트합니다.
            check_col.add(col)
            check_diagonal.add(row - col)
            check_reserve_diagonal.add(row + col)
           
            # 다음 행으로 넘어갑니다.
            back_tracking(row + 1, check_col, check_diagonal, check_reserve_diagonal)
           
            # 원래 상태로 되돌립니다 (백트래킹).
            check_col.remove(col)
            check_diagonal.remove(row - col)
            check_reserve_diagonal.remove(row + col)

# 문제의 해를 찾는 메인 함수입니다.
def solution(N):
    global answer  # 전역 변수 answer를 사용합니다.
   
    # 첫 번째 행에서 백트래킹을 시작합니다.
    back_tracking(0, set(), set(), set())
   
    # 결과를 출력합니다.
    print(answer)

solution(N)