백준 9663번 N-Queen 파이썬 풀이

문제

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

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

---

 

정답 풀이

#N-Queen
#N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
#N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
import sys
n = int(sys.stdin.readline().rstrip())

ans = 0
row = [0] * n

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

def n_queens(x):
    global ans
    if x == n:
        ans += 1

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(ans)

 

풀이 과정

다른 백트레킹 문제와 마찬가지로 1.dfs 2.promising을 활용해야 한다.

 

1.탈출 조건 설계

def n_queens(x):
    global ans
    if x == n:
        ans += 1

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

 

탈출 조건이 아니고 promising을 만족하는경우 depth가 증가하다가  if x == n 일 때의  탈출조건을 설계하였음

 

 

2. promising  조건 설계

def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return False
            
def n_queens(x):
    global ans
    if x == n:
        ans += 1

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

2-1

for 문이 돌면서 첫번째 퀸을 첫번째 열부터 쭉 체크하게 된다.

예를 들어 n =4 이면 (0,0) (0,1) (0,2) (0,3) 을 체크한다.

세로로 내려가면서 체크

2-2 

 

전 단계에 위치해있는 모든 queen의 위치를 체크해야한다 따라서 for 문을 사용하였다. 빨간색의 경우 depth가 0일 때 노란색은 depth가 1일 때 퀸의 위치에 따라 들어갈 수 없는 자리이다.

 

 

 

배운점 &&  공부방향 설정

1. promising 하지 않을 때의 탈출조건을 먼저 설계해야한다.  재귀함수를 사용해야하는 부분은  탈출조건 먼저 설계하는 것이 필요하다.

 

2. 2차원 배열을 사용해야하나 고민하였는데  index를 활용해 1차원 배열로 풀이할 수 있는 idea를 꼭 기억해두자

 

3.퀸의 위치를 첫번쨰,두번째 ... 퀸 으로 누적적으로 고려했어야 했다. 이런 경우 어떤식으로 코드를 짜야하나 머리속에 떠오르지 않았는데, 이럴 땐 for 문을 쓰자.

 

4. 대각선의 조건을 어떻게 정의해야하나 고민하였는데, y축차이 = x축 차이일 때 같은 대각선에 있다는 idea를 기억하자.