[백준 - python] 9663번: N-Queen

문제 링크

9663번: N-Queen

문제 풀이

def isPromising(x):
  for i in range(x):
    if (chess_table[x] == chess_table[i]) or (x - i == abs(chess_table[x] - chess_table[i])):
      return 0
  return 1

def nqueen(x):
  global cnt
  if x == n:
    cnt += 1
    return
  for i in range(n):
    chess_table[x] = i
    if isPromising(x) == 1:
      nqueen(x + 1)

n = int(input())
chess_table = [0 for _ in range(n)]
cnt = 0
nqueen(0)
print(cnt)

9663 입출력 예시

*key point: 백트래킹 시 유망성 판단(isPromising 함수의 역할)을 잘 수행하여 가지치기를 잘 하는 것이 중요하다. 이 문제에서는 chess_table이라는 리스트의 index(체스판의 행)와 값(체스판의 열)을 활용하여 체스판을 구현하고, index의 증가에 따라 이전에 놓았던 퀸과 같은 열 혹은 대각선에 위치하지 않도록 판단해주는것이 핵심이다.