NQueen 문제 파이썬과 자바스크립트 풀이

백준 9663번

9663번: N-Queen

 

✏️ 구상

N*N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치해야한다. 

퀸의 움직임은 직선방향, 대각선방향이다. 그렇다면 생각나는 기본적인 로직은 우리는 퀸을 한줄에 하나씩만 배치할 수 있다는 것이다.

우선 배치한다고 생각해보고 하나씩 손으로 배치를 해보자.

 

<4 x 4 체스판 배치>

첫번째 줄 배치

두 번째 줄 배치

두 번째 줄에선는 1,2번째 칸에 퀸을 배치할  수 없다. 두번째 줄에도 배치했으니 이제 세번째로 넘어간다.

 

세번째줄 배치 불가

세번째줄에 배치가 불가능하다. 따라서 다시 두번째 줄로 돌아가 4번째 칸에 배치한다. (3번째칸 가지치기)

세번째줄 배치 완료

세번째 줄에 퀸을 배치하는 방법은 위 방법이 유일하다. 하지만 이 배치로는 4번째 줄에 퀸을 배치할 수 없다. 따라서 첫번째 줄로 돌아가 첫번째줄 첫번째칸을 가지치기한다.

도출된 해

하나의 해가 도출된다.

 

✏️ 구현

이걸 코드로 옮겨야한다. 첫번째 줄에 퀸을 놓아야 두번째 줄이 결정되고, 두번째가 결정되어야 세번째가 결정되고, 세번째가 결정되어야 네번째가 결정되며 네번째가 결정될 수 있다면 그 값이 해가 된다. 

줄을 깊이(Depth)로 DFS를 구현한다.

 

유망(promising)의 조건1: 같은 열 체크

- col[i] : i 번째 row에서 퀸이 놓여있는 column의 위치

- col[k]: k번째 row에서 퀸이 놓여있는 column의 위치

- col[i]==col[k]: 같은 column에 놓이므로 유망하지 않다.

 

유망의 조건2: 대각선 체크

- abs(열에서의 차이)와 abs(행에서의 차이)가 같다

 

promising 구현

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

 

전체코드

import sys

n=int(sys.stdin.readline())
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 nqueens(x):
  global ans
  # 퀸을 마지막줄까지 배치성공하면 하나의 경우의수를 완성한거다
  if x==n:
    ans+=1
  else:
     for i in range(n):
       row[x]=i
       if is_promising(x):
         nqueens(x+1)
nqueens(0)
print(ans)

 

* 이 코드는 현재 시간초과가 난다. pypy3로도 초과되는상태. 

 

아래는 Node.js로 똑같이 푼 코드이다. 이제 백트랙킹 문제는 자바스크립트로 풀이하려한다.

const readline = require('readline');
const rl=readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', (line)=>{
  const num=Number(line);
  const rows = new Array(num + 1).fill(0);

  const isPromising = (x) => {
    for(let i=1;i<x;i++){
      if(rows[i]===rows[x]||Math.abs(rows[x]-rows[i])===x-i) return false;
    }
    return true;
  };

  let count=0;
  const nqueen = (numOfQueen) => {
    if (isPromising(numOfQueen)){
      if(numOfQueen===num){
        count++;
      } else{
        for(let i=1;i<=num;i++){
          rows[numOfQueen+1]=i;
          nqueen(numOfQueen+1);
        }
      }
    }
  };
  nqueen(0);
  console.log(count);
});