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

백준 9663 N-Queen

백트래킹 문제다. grid를 만들고 방문했지는 확인할까 고민하다가 조금 더 간단하게 해결할 수 있을 것 같아서 set을 활용해서 코드를 작성했다. 방문이 가능한 요소들을 set에 담고 삭제했다가 다시 추가하는 식으로 코드를 작성했다.

1. 대각선 중에 겹치는 것이 없는지 확인할 set 2개와 x축을 저장할 set 1개 총 3개의 set를 선언한다.
2. 해당 위치에 퀸을 놓을 수 있다면 set에서 모든 요소를 삭제하고 재귀문에 들어간다.
3. 재귀문 탈출 이후에 다시 set에 요소를 추가하여 set을 복구한다.

def DFS(y, q) -> int:
    if q == n:
        return 1
    res = 0
    l = list(s3)
    for i in l:
        if y + i in s1 and y - i in s2 and i in s3:
            s1.discard(y + i)
            s2.discard(y - i)
            s3.discard(i)
            res += DFS(y + 1, q + 1)
            s1.add(y + i)
            s2.add(y - i)
            s3.add(i)
    return res

n = int(sys.stdin.readline().strip())
s1 = set(range(2 * n - 1))
s2 = set(range(1 - n, n))
s3 = set(range(n))
print(DFS(0, 0))