[백준] [Python] 🧩 N-Queen (Easy) 30242번

import sys


def q_check(x):
    # 이미 기록된 0 ~ N 범위 보기
    for i in range(N):

        # 본인 단계 제외
        if i==x:
            continue

        # 아직 안쓴거는 대각선 영향갈수있으니 제외
        if row[i]==0:
            continue

        # row (가로)체크
        # 체크하려는 row == 기록된 row(q_list[i]) 일때 False
        if row[x] == row[i]:
            return False
        # 대각선 체크
        # 체크하려는 row 와 이미 기록된 row 의 차가
        # 체크하려는 column 과 기록된 column 의 차랑 같다면 대각선이니 False
        if abs(row[x]-row[i]) == abs(x-i): # abs() = 절댓값 함수
            return False
    # 두 경우 다 피해가면 True
    return True


def n_queen(n):
    # 끝까지 완성한 경우
    if n==N:
        print(*row)
        quit() # 아예 종료

    # 이미 써있는경우 바로 다음단계로
    if row[n]!=0:
        n_queen(n+1)
        return

    # 1부터 N까지 넣어보기
    for i in range(1,N+1):
        # 해당 숫자를 사용하지 않았을 때만 넣기
        if visited[i] == False:
            temp = row[n]
            row[n] = i
            if q_check(n):
                visited[i]=True
                n_queen(n+1)
                visited[i]=False
            row[n] = temp

N = int(sys.stdin.readline())
row = list(map(int, sys.stdin.readline().split()))
visited = [False] * (N+1)

# 이미 놓아진 퀸의 값
for i in range(N):
    if row[i] != 0:
        visited[row[i]] = True

n_queen(0) # 0번째 줄부터 함수 실행
print(-1)

import sys

def backtracking(n):

    # 다 도달했을 때
    if n==N:
        print(*arr)
        quit()

    # 이미 써있는경우 바로 다음단계로
    if arr[n] != 0:
        backtracking(n + 1)
        return

    for i in range(N):
        # 놓을 수 있으면
        if row[i] and x1[i+n] and x2[i+((N-1)-n)]:

            arr[n] = i+1
            row[i]=False # 가로줄 제거
            x1[i+n]=False # 오른쪽 위 방향 대각선 제거
            x2[i+((N-1)-n)]=False # 오른쪽 아래 방향 대각선 제거

            # 자식 노드로 이동
            backtracking(n+1)

            # 백트래킹
            row[i]=True
            x1[i+n]=True
            x2[i+((N-1)-n)]=True
            arr[n] = 0

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

row = [True]*N # 가로
x1 = [True]*(2*N) # 제일 왼쪽이 인덱스인 우상향 대각선
x2 = [True]*(2*N) # 제일 오른쪽이 인덱스인 우하향 대각선

for i in range(N):
    if arr[i] != 0:
        row[arr[i]-1] = False  # 가로줄 제거
        x1[arr[i]-1 + i] = False  # 오른쪽 위 방향 대각선 제거
        x2[arr[i]-1 + ((N - 1) - i)] = False  # 오른쪽 아래 방향 대각선 제거

backtracking(0)
print(-1)

x2[i+((N-1)-n)] = False 로 바꿔주어 대각선이 사용되었음을 나타내면 된다.

x2[i+((N-1)-n)] 가 True면 겹치지 않고, False면 겹쳐서 불가능 한것이다.

x1[i+n] = False 로 바꿔주어 대각선이 사용되었음을 나타내면 된다.

x1[i+n] 가 True면 겹치지 않고, False면 겹쳐서 불가능 한것이다.