백준 9663. N-Queen

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

9663번: N-Queen

import sys
input = sys.stdin.readline
N = int(input())
board = [0]*N # 보드판(퀸이 놓이는 열의 위치를 기록) [1,3,2,4]면 퀸이 (0,1), (1,3), (2,2) (3,4)에 놓였다는 의미
cnt = 0

# 백트래킹
def isPromising(x):  # x는 현재 행
    for i in range(x):  # 이전 퀸들이 놓였던 행들만 검사하면 됨(범위가 0~x-1인이유)
        # 다른 퀸과 열이 같거나, 대각선이면 False
        if board[x] == board[i] or abs(board[x] - board[i]) == x-i:
            return False
        # 전자: 현재 퀸의 열 = 이전에 놓인 퀸의 열?
        # 후자: 현재 퀸의 열과 이전에 놓인 퀸의 열의 차이 = 현재 퀸의 행과 이전에 놓인 퀸의 행의 차이
        # 간단하게 말하면 행과의 차이, 열과의 차이가 같으면 대각선
    return True

# DFS 탐색(열 우선 탐색)
def dfs(x):
    global cnt # res: N개의 퀸을 놓는 경우의 수

    # 보드판 맨 끝에 도달해서 탐색마침(N개의 퀸 놓는 가짓수 +1)
    # 모든 행에 퀸을 놓았을 경우
    if x == N:
        cnt += 1
        return

    # 아직 탐색할 행이 남음
    else:
        # 해당 행의 1~N열 칸을 탐색
        for i in range(N):
            # x행, i열 탐색
            board[x] = i
            # 해당 칸이 다른 퀸이 겹치지 않는지 판별
            if isPromising(x):
                dfs(x+1)  # 겹치지 않으면 다음 행으로 이동
# 출력
dfs(0)
print(cnt)

pypy로 제출해야 시간초과 안나는...

대표적인 백트래킹 문제라고 한다!