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

[백준] 9663번: N-Queen

백트래킹 알고리즘의 기본인 N-Queen 문제이다.

문제 팁

1. 2차원 배열이 아닌, 1차원 배열로도 가능하다.
2. 퀸을 놓을 수 있는지 없는지 확인하는 함수를 만든다.
3. 퀸을 못 놓는 경우
   
   • 같은 열에 다른 퀸 존재
   • 대각선에 다른 퀸 존재

---

n = int(input())
cnt = 0
# 체스판 리스트 초기화
li = [0] * n

# 퀸을 놓을 수 있는지 없는지에 따라, 그 경우가 유망한지를 판별하는 함수
def isPromising(x):
    for i in range(x):
        if li[x] == li[i] or abs(li[x] - li[i]) == abs(x - i):
            return False
        
    return True

def dfs(x):
    global cnt
    if x == n:
        cnt += 1
        return
    
    for i in range(n):
        li[x] = i
        if isPromising(x):
            dfs(x+1)
            
            
dfs(0)
print(cnt)