★Backtracking Upper-Advanced I - 1 Solved★

★ 9663 N-Queen ★

 

#n-queens
#place n queens (not placed in the same row / col / diagonal dir)
def track(x):
    global ans
    if x == N: #finished
        ans+=1
        return
    else:
        for ny in range(N):
            if v1[ny] == v2[x+ny] == v3[x-ny] == False:
                v1[ny] = v2[x+ny] = v3[x-ny] = True
                track(x+1)
                v1[ny] = v2[x+ny] = v3[x-ny] = False         
N=int(input())
ans=0
v1=[False]*(N) #horizontal 0~(N-1)
v2=[False]*(2*N-1) #diagonal (right->left) 0 ~ 2*N-2
v3=[False]*(2*N-1) #diagonal(left->right) -(N-1) ~ (N-1)
track(0)
print(ans)

 

🙀 NxN 체스판에서 위/아래/대각선 방향으로 같은 queen이 놓이지 않게 배치하는 well-known 문제. 여러 방법 중 backtracking 방법으로 진행. 총 3개의 visited를 만들어 tracking 한다는 특정 idea가 필요. DFS로 depth마다 진행하므로 같은 행은 고려할 필요 없음. 같은 열에 있는 지 알아보기 위해 y index로 구성된 v1 list (0~N-1) / 왼쪽 아래로 향하는 대각선 방향에 같이 있는 지 알아보기 위해 v2 list(0~2*N-2): x index와 y index의 합 / 오른쪽 아래로 향하는 대각선 방향에 같이 있는 지 알아보기 위해 v3 list(-(N-1)~(N-1)): x index - y index / 아래 그림에서 파란색 화살표 v2 list로 x와 y 좌표의 합이 동일한 규칙. 빨간색 화살표 v3 list로 x - y가 동일한 규칙

→ 현재 x 에서 ny만 0~N-1까지 이동하며 v1[ny]와 v2[x+ny]와 v3[x-ny]가 모두 False일 경우만 track() 진행(재귀 구현). 그렇지 않다면 backtracking. track() 이후 빠져나올 때 모두 True 후처리 필요.

→ tracking할 때 필요한 핵심인자만 최대한 돌려 메모리 초과 / 시간 초과 방지 

---