백트래킹의 기본, N-QUEENS 아이디어와 코드를 쉽게 이해해보자 (python)

 

 



✍️  N-QUEENS

크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제

N이 주어졌을때, 퀸을 놓는 방법의 수는 모두 몇개인가?

 

 

---

 

 

 

먼저 퀸을 어디에 놓을지 결정하는 과정 속에서, 

해당 위치를 저장할 곳이 필요하다

 

 

✅ rows 배열

1차원으로도 충분히 퀸의 위치를 저장할 수 있다.

체스판의 크기를 N*N이라고 생각했을 때, rows 배열은 N의 크기를 갖는 1차원 배열이다.

 

 

 

rows[i] = j  

i행, j열에 퀸이 놓여있다는 의미

 

아래 그림을 보면 rows[0] 에 1이 들어있는데,  

0행 1열에 퀸을 배치한것이다.

 

 

 

---

 

 

이제 행을 하나씩 증가시키면서 퀸을 배치시켜보자.

 

 

✅ put_queen (r)

특정 행 (r)에 퀸을 놓는 함수이다.

 

 

하나씩 행을 증가시키면서 놓을수 있는 자리를 만나면 다음행을 놓게 된다.

이때 함수 자신을 호출하면서 재귀하게 된다.

 

 

탈출 조건 : 

r == n이 되면 마지막 행에 퀸을 놓은것으로 판단,

answer을 증가시키고 return해준다.

 

 

for i in range(n) > 여기서 n번 반복하는것은 열에 해당한다.

rows[r] = i 이 코드를 통해 퀸을 [r행, i열]에 놓게 된다.

 

놓았을 때 is_valid(r) 함수를 호출해보고,

여기서 True값이 반환되면 놓을 수 있는 위치이기 때문에

put_queen을 호출하며 다음 행으로 넘어간다.

 

 

 

---

 

✅  is_valid (r) 

현재 r행에 놓은 위치가 유효한지 (상하좌우 대각선에 퀸이 존재하는지) 체크하는 함수이다.

 

 

여기에서 

1) 같은 열에 퀸이 존재하는가

2) 대각선 상에 퀸이 존재하는가

 

2가지만 체크하게 되는데 이는

 

이전에 행을 1개씩 증가시키면서 퀸을 놓아왔기 때문에 

행에선 겹칠 수 없기 때문이다.

 

 

for i in range(r): 

지금까지 r행까지 퀸을 놓았기 때문에 r보다 큰 위치엔 퀸이 전혀 존재하지 않는다. 

따라서 for문은 r까지만 돌리며 i행과 r행을 비교하게 된다.

 

 

1) 열의 비교   (같은 열에 퀸이 존재하는가)

 

rows[i] == rows[r]

 

i행에 놓인 열의 값과,  r행에 놓인 열의 값을 비교했을 때 

값이 같으면 같은열에 존재하는것이다!  

 

 

아래 그림을 다시 봐보면 좀더 이해하기 쉽다.

 

2) 대각선의 비교   ( 대각선 상에 퀸이 존재하는가 )

abs( r - i )  == abs( rows[i] - rows[r] ) 

 

이 두 값이 같으면 같은 대각선 상에 있는것으로 판단할 수 있다.

 

 

 

같은 대각선에 위치하면, 두 점의 행차이/ 열차이는 항상 같다

 

 

아래 그림을 통해 직접 눈으로 확인해보자.

 

 

 

✅ 코드

import math

n = int(input())
answer = 0
rows = [0] * n

def is_valid(r):
    for i in range(r):
        if rows[i] == rows[r]:
            return False
        if abs(r-i) == abs(rows[r]-rows[i]):
            return False
    
    return True
        
def put_queen(r):
    global answer
    if r == n :
        answer+=1
        return
    
    for i in range(n):
        rows[r] = i
        if is_valid(r):
            put_queen(r+1)
    
put_queen(0)
print(answer)a

 

 

 

아래는

N-Queen 문제를 풀어볼 수 있는 링크이다.

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

 

 

---