BOJ [NQueen]

문제

2022-03-20

문제보기

풀이

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

 
def dfs(x):
    global result
 
    if x == N:
        result += 1
    else:
       
        for i in range(N): 
            row[x] = i
            if adjacent(x): 
                dfs(x + 1)
 
N = 8
row = [0] * N
result = 0

dfs(0)

print(result)

nQueen 문제의 핵심은 체스판을 이차원 배열로 모두 저장할 필요가 없다는 것이었다.

각 row마다 queen은 한개만 존재할 수 있으므로

row = [] 에다가 row를 차례대로 탐색하면서 퀸의 x좌표를 하나씩

append하고 row의 길이가 n이되면 정답처리를 하는 식이다.

위에서 아래로 퀸을 놓으므로 y칸에 퀸을 놓을 수 있나 확인하는 과정은

0~y-1칸의 퀸 위치를 담은 row를 다 탐색해서 대각선과 위아래 양옆을 제거해주면 된다.

또한 대각선에 위치하는 말을 check 할때

abs 를 사용해서 x축의 차와 y축의 차의 절대값이 같으면 대각선에 있는 것으로 간주한다.