백준 9663: N-Queen - 백트래킹(파이썬)

N-Queen 성공

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

내 코드

import sys

def func(x): #x번째 줄에 대한 것.
    global cnt
    if x==n: #x가 n이 될 때까지 재귀했으면,
        cnt+=1 #n queen 상태를 만든 것임.
        return

    for y in range(n): #y좌표는 0~n 가능
        flag=True #특정 y좌표에 대해 불가능하면 False로 바꿀 것임.

        for nx in range(x): #현재 x좌표보다 위에 있는 놈들에 대해 검사
            if arr[nx]==y or x+y==arr[nx]+nx or x-y==nx-arr[nx]: #같은 세로 or 오른쪽 위 대각선 or 왼쪽 위 대각선 상에 있으면,
                flag=False #n queen 불가능.
                break #더 이상 비교할 필요 X

        if flag:
            arr.append(y) #현재 y 좌표를 append.(유명한 y좌표)
            func(x+1) #다음 줄에 대해 재귀.
            arr.pop() #함수가 종료되면 append 했던 y를 pop.
            

#메인 코드 부분
n=int(sys.stdin.readline())

cnt=0
arr=[]

func(0)

print(cnt)

 

풀이 및 접근)

- n queen은 기본적으로 한 줄에 하나씩 놓인다. 이를 재귀할 때 염두해 둔다.

- 위의 조건을 제외하면, 같은 세로줄, 오른쪽 위 대각선, 왼쪽 위 대각선에 겹치면 안된다.

- 오른쪽 위 대각선은 같은 대각선에 있는 x좌표+y좌표 의 값이 모두 같고, 왼쪽 위 대각선은 같은 대각선에 있는 x좌표-y좌표 의 값이 모두 같다. 이를 활용하여 조건을 만들면 된다.

- arr[ ] 리스트에 각 줄별 y좌표를 저장할 것이다. arr[0]에는 첫번째 줄의 y좌표가, arr[1]에는 두번째 줄의 y좌표가, arr[2]에는 ...

- 위에서 말했던 조건을 만족하면 arr[ ]에 y좌표를 저장하고 func( ) 함수를 재귀한다.

- 함수를 나오고 나서는 append한 해당 y에 대한 것이 끝났으므로 pop을 한다.

- 조건에 대한 코드를 함수로 빼면 더 보기 좋은 코드가 된다.

 

 

조건 확인을 함수로 빼낸 코드

import sys

def isPromising(x,y):
    for i in range(x):
        if arr[i]==y or x+y==arr[i]+i or x-y==i-arr[i]:
            return False

    return True


def func(x):
    global cnt
    if x==n:
        cnt+=1
        return

    for y in range(n):
        if isPromising(x,y):
            arr.append(y)
            func(x+1)
            arr.pop()


#메인 코드 부분
n=int(sys.stdin.readline())

cnt=0
arr=[]
func(0)

print(cnt)