[백준] 9663 "N-Queen" -python

 

 

알고리즘

 대각선에 퀸이 존재하는지 여부를 체크하는 배열 2개와 같은 행에 퀸이 존재하는지 여부를 따지는 배열 1개를 두고 백트래킹을 실행한다. 종료조건은 행을 1번씩 늘리면서 행번호가 입력 N과 같은 경우이다.

 

소스코드

import sys
N = int(sys.stdin.readline())

result = 0
isused1 = [0] * N
isused2 = [0] * (N * 2)
isused3 = [0] * (N * 2)

def func(k):
    global result
    if k == N:
        result += 1
        return 
    for i in range(0, N):
        if isused1[i] or isused2[k+i] or isused3[k-i+N-1]:
            continue    
        isused1[i] = 1
        isused2[k + i] = 1
        isused3[k - i + N - 1] = 1
        func(k+1)
        isused1[i] = 0
        isused2[k + i] = 0
        isused3[k - i + N - 1] = 0

func(0)
print(result)

 

느낀점

 처음 문제를 보고 NxN 행렬을 만들어서 행을 내려가면서 퀸을 놓은때 마다 행, 우대각, 좌대각선을 모두 false로 처리하는 방식으로 백트래킹을 진행하였으나 시간초과가 나서 이후 바킹독님의 알고리즘을 참고하여 현재 좌표관점으로 대각선에 퀸이 존재하는지 여부를 파악할 수 있다는 것을 알게되었다.

 

참고 : https://blog.encrypted.gg/945