[백준] 9663 - N-Queen (Python)

문제 출처:

www.acmicpc.net/problem/9663

9663번: N-Queen

문제 풀이:

• 사실 풀다가 대각선 부분을 어떻게 해결해야할지몰라서 (아래에서 위로) 결국 풀이를 좀 보고 풀었다.
• 각 줄에 우선적으로 1개를 두고 그후 각 대각선 에 놓을 수 없는 자리에 check를 해둔 후에 재귀를 통해서 해결한다.
• 풀이에도 자세히 나와있지만 (x,y)에 놧을경우 같은 대각선인 경우는  x+y 가 같은경우, x-y가 같은경우(이경우엔 음수처리를 해주어야 한다) 를 보면 같은 대각선을 알 수 있다.

cnt=0
isused1 = [0]*40
isused2 = [0]*40
isused3 = [0]*40


def func(cur):
    global n,cnt

    if(cur==n):
        cnt+=1
        return

    for i in range(0,n):
        if(isused1[i] or isused2[i+cur] or isused3[cur-i+n-1]):
            continue
        isused1[i]=1
        isused2[i+cur]=1
        isused3[cur-i+n-1]=1
        func(cur+1)
        isused1[i] = 0
        isused2[i + cur] = 0
        isused3[cur - i + n - 1] = 0


if __name__ == "__main__":
    n = int(input())
    func(0)
    print(cnt)

* Python으로 제출하면 시간초과가 뜬다.. Pypy3는 되는데 시간복잡도가 O(n!)이지만 가지치기를 통해서 꽤나 잘 돌꺼라고 생각햇는데 아닌가 보다..