문제 링크: https://www.acmicpc.net/problem/9663

크기가 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 퀸을 놓는 방법의 수를 구하자

퀸은 위 사진과 같은 열 또는 같은 행으로 체스판의 끝까지, 대각선 방향으로 체스판의 끝까지 이동이 가능하다. 그러므로 서로 공격할 수 없도록 퀸을 놓기 위해서는 빨간색으로 표시되지 않은 칸에 퀸을 두어야 한다.

1️⃣ 예시

아래와 같이 4 X 4 보드가 있다고 가정하고 4개의 퀸을 서로 공격할 수 없도록 배치해보자.

예시 1

1. (0, 0)에 퀸을 하나 둔다
   • 핑크색으로 표시한 칸에는 다른 퀸을 둘 수 없음
   • 두 번째 줄에서는 (1, 2), (1, 3) 두 곳에 퀸을 둘 수 있음
     
     
2. (1, 2)에 퀸을 둔다
   • 빨간색으로 표시한 칸에는 다른 퀸을 둘 수 없음
     
     
3. 세 번째 줄에서는 퀸을 둘 수 없음
   
   
4. (1, 3)에 퀸을 둔다

→ 퀸을 4개 놓는 것이 불가능

예시 2

1. 이번에는 (0, 1)에 퀸을 놓아보자
   • 두 번째 줄에서는 (1, 3)에 퀸을 둘 수 있음
     
     
2. (1, 3)에 퀸을 둔다
   • 세 번째 줄에서는 (2, 0)에 퀸을 둘 수 있음
     
     
3. (2, 0)에 퀸을 둔다
   • 네 번째 줄에서는 (3, 3)에 퀸을 둘 수 있음
     
     
4. (3, 3)에 퀸을 둔다

→ 서로 공격하지 못하도록 퀸을 4개 배치하는 것에 성공! 경우의 수를 1 증가시킨다

2️⃣ 문제 풀이 포인트

• 한 줄에는 하나의 퀸만 둘 수 있다.
  • 0개 안됨 🚫 → 퀸 N개를 배치할 수 없음
  • 2개 이상도 안됨 🚫 → 퀸끼리 서로 공격이 가능하게 됨
    
    
  • 만약 다음 줄에 퀸을 둘 수 있는 자리가 없다면? 윗 줄로 이동하여 퀸의 위치를 옮기자
    
    
• 각 줄에서 퀸이 어디 있는지가 핵심 포인트 ‼️
  • 보드 문제이기 때문에 처음 문제를 풀면 2차원 배열로 문제를 푸려고 시도할 것이다.
  • 하지만 1차원 배열에서, 인덱스를 행 번호, 값을 열 번호 로 사용하여 문제를 풀 수 있다.
    위에서 했던 예시를 1차원 배열로 표현하면 아래와 같이 표현할 수 있다.
  • 예시 1: [0, 2, 1, -] (마지막 행에는 퀸을 둘 수 없기 때문에 '-'로 표시하였다)
  • 예시 2: [1, 3, 0, 2]
    
    
• 그러면 다음 줄에 퀸을 둘 수 있는지 판단이 필요하다! 다음 줄에 퀸을 둘 수 없는 경우는 뭐가 있을까?
  • 나와 같은 열 → 번호가 같은지 비교
  • 나의 대각선 열 → 열 번호의 차이 == 행 번호의 차이

3️⃣ 문제를 풀어보자

♟️ 입력

import sys

input = sys.stdin.readline

n = int(input())

• 파이썬에서는 시간 단축을 위해 readline() 함수를 사용

♟️ 변수

queen_col = [0 for _ in range(n)] # 퀸의 위치를 나타내는 배열
count = 0 # 경우의 수

♟️ 다음 줄에 퀸을 둘 수 있을지?

• 나와 같은 열 → 번호가 같은지 비교
• 나의 대각선 열 → 열 번호의 차이가 행 번호의 차이

def promising(row):
    for i in range(row):
        if queen_col[row] == queen_col[i] or abs(queen_col[row] - queen_col[i]) == row - i:
            return False
    return True

♟️ 백트래킹

• 재귀 활용
• 파이썬에서는 global 키워드를 사용하여 내부에서 전역 변수를 사용

def nqueen(row):
    if row == n: # 마지막 줄까지 탐색 완료
        global count
        count += 1
        return
    
    for col in range(n):
        queen_col[row] = col # (row, col)에 퀸을 놓는다

        if promising(row): # 다음 줄에 퀸을 놓을 수 있다면
            nqueen(row+1) # nqueen()을 호출하여 퀸을 놓는다

♟️ 전체 코드

import sys

input = sys.stdin.readline

# 1. 입력
n = int(input())

# 2. 변수
queen_col = [0 for _ in range(n)] # 퀸의 위치를 나타내는 배열
count = 0 # 경우의 수

# 3. 다음 줄에 퀸을 둘 수 있을지 판단하는 함수
def promising(row):
    for i in range(row):
        if queen_col[row] == queen_col[i] or abs(queen_col[row] - queen_col[i]) == row - i:
            return False
    return True

# 4. 백트래킹
def nqueen(row):
    if row == n:
        global count
        count += 1
        return
    
    for col in range(n):
        queen_col[row] = col

        if promising(row):
            nqueen(row+1)

# 5. 위에서 구현한 함수를 호출하여 답을 구한다
nqueen(0)
print(count)