백준(baekjoon) 9663번: N-Queen(골드 4, 파이썬 PYTHON) - 백트래킹

문제

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

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

 

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

9663번: N-Queen

 

import sys

N=int(sys.stdin.readline())
chess_board=[]
count=0

def promising(num):
  global chess_board
  for x in range(len(chess_board)): 
    if(len(chess_board)-x==abs(chess_board[x]-num)): 
      return False
  return True 

def backtracking(num): 
  global N,chess_board,count
  if(num==N): 
    count+=1  
  else: 
    for x in range(N): 
      if(x not in chess_board):  
        if(promising(x)==True):  
          chess_board.append(x)  
          backtracking(num+1) 
          chess_board.remove(x)  
      
backtracking(0)
print(count)

 

※ 백트래킹

 

 

● 먼저 chess_board 배열과 경우의 수를 세는 count 변수를 설정해준다.

chess_board 배열의 인덱스는 체스판에서의 행의 위치를, 요소의 값들은 체스판에서의 열의 위치를 나타낸다.

 

함수 backtracking 을 정의해주자.

 

● 먼저 매개변수 num은 현재 체스판에 놓여있는 퀸의 개수를 나타낸다.

 

● 만약 num의 값이 N과 같아지게 되면 체스판에 N개의 퀸을 놓는데 성공했다는 것이므로 count를 1 증가시켜준다.

 

● num 이 N보다 작으면 0부터 N-1까지의 수를 돌며 각 수가 현재 chess_board 배열에 들어있지 않고(현재 놓으려는 위치와 같은 열에 이미 퀸이 놓여있지 않고), 이 수를 promising 함수에 넣어 True가 반환되면 chess_board 에 이 수를 append 한 후, 퀸에 하나 더 놓여진 것이므로 bactracking(num+1) 을 호출해준다.

 

● 다 끝나면 append 한 수를 다시 remove 해준다.

 

promising 함수는 안에서는 어떤 일이 일어날까??

 

● 현재 chess_board 안에 들어있는 요소들을 돌며 각 요소가 들어있는 인덱스 값과 배열에 append 하려는 위치의 인덱스 값의 차이, 각 요소의 값과 들어온 매개변수의 값의 차이, 이 두 차이의 값이 같으면(현재 놓으려는 퀸의 위치와 같은 대각선 상에 이미 퀸이 놓여져있으면) False를 return 해준다.

 

● 두 차이의 값이 다르면 True를 return 해준다.

 

● 맨 처음에는 퀸의 개수가 0 이므로 backtracking(0) 을 호출해준다. 그 이후 count를 출력해주면 답이 나온다!!

 

PyPy3로 제출하였다.

 

 

결과

 

 

♣ 참고: N-Queen 알고리즘

https://tear94fall.github.io/lecture/2020/09/16/n-queen-problem.html

[Algorithm] N-Queen 문제