백준 9663 N-Queen

failed

틀린 답

import sys
input = sys.stdin.readline

n = int(input())

queens = [[False] * n for _ in range(n)] #False 자리에만 올 수 있음
cnt = 0

def visit(x, y, visiting):
    for i in range(n):
        queens[i][y] = True if visiting else False
        queens[x][i] = True if visiting else False
        if (0 <= x - i) and (0 <= y - i):
            queens[x - i][y - i] = True if visiting else False
        if (x + i < n) and (y + i < n):
            queens[x + i][y + i] = True if visiting else False

def dfs(depth, x, y):
    global cnt
    if depth == (n - 1):
        cnt += 1
        return
    if (x == n - 1) and (y == n - 1):
        return
    for i in range(x, n):
        for j in range(y, n):
            if not queens[i][j]:
                visit(i, j, True)
                dfs(depth + 1, i, j)
                visit(i, j, False)

dfs(0, 0, 0)
print(cnt)

어제 백트래킹 dfs에서 한계를 느끼고 오늘 조져보겠다 다짐..
nxm은 파이썬에서 너무 쉬워서 5분만에 풀었지만 n-queen에서 조져지는건 나였다

답

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n = int(input())

row = [0] * n
cnt = 0

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

def backtracking(x):
    global cnt
    if x == n:
        cnt += 1
        return
    for i in range(n):
        row[x] = i
        if is_promising(x):
            backtracking(x + 1)

backtracking(0)
print(cnt)

원리를 이해하니 굉장히 간단하면서도 당연했다.
백트래킹이란 이런거군..!