[Python]백트래킹 백준 9663

   문제

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

백트래킹을 이용한 문제의 기본이라고 한다.

가장 먼저 떠오르는 방법은 퀸의 자리를 하나 잡고 한줄씩 내려가면서 위와 대각선을 확인

하여 퀸이 없다면 자리를 확정하며

마지막줄까지 퀸의 자리를 확정짓는다면 수를 1씩늘리는 방법이다.

9663.py

굉장히 코드가 지저분하고 느리다. 시간초과가 뜬다. pypy3으로 제출하면 성공하기는 한

다.함수의 사용을 통해 조금은 정리해보고 색다른 방법을 통한 코드도 올려볼려고한다.

 함수를 통해 넘어가는 경로에 퀸이 있을때 다음칸으로 넘어가는 부분을 깔끔하게 

정리했다.

9663(2).py

마지막 방법은 아래 사이트를 참조하였다.

https://rebas.kr/761

정말 똑똑한 사람들은 많은것같다....

n=int(input())
count=0
 
row,left,right=[0 for _ in range(n)],[0 for _ in range(2*n-1)],[0 for _ in range(2*n-1)]#수직,왼쪽대각선,오른쪽 대각선
#인덱스의 합과 차가 같은 대각선상에 있을때 같다는 것을 이용함
#ex)0,2과 1,1과 2,0은 같은 대각선 상에 위치한다. 각행열의 합이 같은것을 알수있다.
 
def queenlocation(index):
    global count
    if index==n:    #끝까지 퀸을 넣으면
        count+=1
        return
    for col in range(n):  #열을 이동하며
        if row[col] + left[index+col] + right[n-1+index-col]==0: #세조건에 걸리지 않는다면
            row[col]=left[index+col]=right[n-1+index-col]=1
            queenlocation(index+1)
            row[col]= left[index+col]= right[n-1+index-col] = 0#초기화
 
queenlocation(0)
print(count)

코드도 간결하고 속도또한 훨씬빠르다. 하지만 파이썬으로 제출시 시간초과가뜬다.

파이썬의 한계가 들어나는 부분이 아닐까싶다.pypy3으로 제출하여야 성공할수있다.

가장 빠른방법은 미리 답을 구해서 배열에 저장후 출력하는 방법일것이다.

N이 14이하이기때문에 이렇게 답을 제출하는방법도 하나의 방법이 될수있다.