[백트래킹] 백준 9663번: N-Queen

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

9663번: N-Queen

백트래킹으로 잘 알려진 문제다. 

n = int(input())
graph = [[0 for _ in range(n)] for _ in range(n)]

global cnt
cnt = 0

def isPossible(x, y, num):
    for i in range(n): # row and col
        graph[i][y] += num

    # diagonal
    for i in range(n):
        if 0<=i<n and 0<=y-x+i<n:
            graph[i][y-x+i] += num

        if 0<=x+y-i<n and 0<=i<n:
            graph[x+y-i][i] += num


        graph[x][y] -= 2*num

def dfs(i):
    global cnt
    if i == n:
        cnt += 1
        return

    for j in range(n):
        if graph[i][j] == 0:
            isPossible(i,j,1)
            dfs(i+1)
            isPossible(i,j,-1)


## 대칭성을 이용!! 첫번째 dfs 범위를 제한해주자.
if n%2 == 0:
    for j in range(n//2):
        if graph[0][j] == 0:
            isPossible(0,j,1)
            dfs(1)
            isPossible(0,j,-1)
    print(2*cnt)
else:
    for j in range(n//2):
        if graph[0][j] == 0:
            isPossible(0,j,1)
            dfs(1)
            isPossible(0,j,-1)

    ans = 2*cnt
    cnt = 0

    j = n//2
    if graph[0][j] == 0:
        isPossible(0,j,1)
        dfs(1)
        isPossible(0,j,-1)

    print(ans+cnt)

35번째 줄을 보면 대칭성을 이용했다는 말이 나오는데,

N개의 퀸을 놓는 특정 경우에 대해 그 대칭인 케이스도 무조건 가능할 것이기 때문에

 

i가 0, 즉 첫번째 행에서 dfs를 모든 열에 대해 하지 말고 절반만 해준다.

그리고 2배를 해주면 최종 결과가 된다.