N-Queen

풀이

 N-Queen은 백트래킹으로 가장 유명한 문제 중 하나이다. 처음에는 방문 처리로 2차원 배열을 사용해 이중 반복문을 돌려서 원소 하나당 6방향으로 DFS를 돌리려고 했다. 하지만 굉장히 비효율적이고 시간초과 판정이 뜰거 같았다. 어차피 가로에 1개의 체스 말만 둘 수 있기 때문에 더 효율적인 방법이 있을 거라 생각했고 방문 처리 visited 배열을 v1(가로, x), v2(좌상단 ~ 우하단, y-x), v3(좌하단 ~ 우상단, x+y) 3개로 설정해 백트래킹을 돌려서 풀었다.

N = int(input())

v1 = [False]*(N)
v2 = [False]*(2*N-1)
v3 = [False]*(2*N-1)
ans = 0
def dfs(x):
    global ans
    if x == N:
        ans += 1
        return
    for y in range(N):
        if not v1[y] and not v2[y - x] and not v3[x + y]:
            v1[y], v2[y - x], v3[x + y] = True, True, True
            dfs(x+1)
            v1[y], v2[y - x], v3[x + y] = False, False, False

dfs(0)
print(ans)

시간 복잡도 : O(N!)