[백준][20단계 백트래킹] 9663번 /N-Queen (파이썬/Python)

1. 문제 설명

https://www.acmicpc.net/problem/9663

2. 코드

import sys
input = sys.stdin.readline

N = int(input().strip())

cols  = [False] * N           # 사용 중인 열
diag1 = [False] * (2*N - 1)   # r + c
diag2 = [False] * (2*N - 1)   # r - c + (N-1)

def dfs(r: int) -> int:
    if r == N:
        return 1
    cnt = 0
    for c in range(N):
        d1 = r + c
        d2 = r - c + (N - 1)
        if cols[c] or diag1[d1] or diag2[d2]:
            continue
        cols[c] = diag1[d1] = diag2[d2] = True
        cnt += dfs(r + 1)
        cols[c] = diag1[d1] = diag2[d2] = False
    return cnt

print(dfs(0))

3. 풀이 과정

퀸은 상하좌우 대각선까지 공격이 가능하다.

대각선은을 우상향이랑 우하향으로 나누어서 확인한다.

우상향은 r+c로 같은 값이 나오는 위치들로 파악하고,

우하향은 r-c+(N-1)로 같은 값이 나오는 위치들로 파악한다.

N*N로 행의 개수 r이 N이 되면 1을 반환해서 cnt에 1을 더한다.

카운트는 0부터 시작한다.

for문으로 열c를 받는다.

우상향d1과 우하향d2를 계산하고,

상하, 대각선을 확인해서 True 값이 있으면 continue로 넘어간다.

없으면 상하,대각선을 전부 Ture로 초기화한다.

다음 열r+1로 넘어가서 r==N이 될때까지 재귀한다.

재귀가 끝나면 상하,대각선을 False로 초기화하고 다음 열 c+1을 확인한다.

모든 과정이 끝나면 cnt를 반환한다.

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심