[백준 9663 / Python] N-Queen

N-Queen

🔍 알고리즘 분류

• 백트래킹

💡 문제 풀이

1차원 배열로도 구현 가능

1. row[x]=i는 (x행, i열)에 퀸이 놓여있다는 뜻
2. 유망성 판단은 현재 행인 x전까지 놓여있는 퀸 확인
   1) 같은 열에 놓여있는지 확인
   2) 대각선에 놓여있는지 확인: 행 차이==열 차이
3. 행이 n에 도달했을때 답 추가

📄 코드

n = int(input())

answer = 0
row = [0] * n

def is_promising(x):
    for i in range(x):
        if row[i] == row[x] or abs(i - x) == abs(row[i] - row[x]):
            return False
    return True

def dfs(x):
    global answer
    if x == n:
        answer += 1
        return
    for i in range(n):
        row[x] = i # x행 i열
        if is_promising(x):
            dfs(x + 1)

dfs(0)     
print(answer)

• 시간복잡도: O(N!)