[Alogorithm] N-Queen 문제 ( 백트래킹-Backtracking / Javascript, Python )

 

N-Queen 문제는 백트래킹을 사용해서 문제를 푸는 대표적인 문제이다.

 

N-Queen 문제는 딱 한 문장으로 설명이 가능하다

[ 크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경의 수를 구하는 문제 ] 이다.

 

 

 

---

 

 

 

백트래킹이란?

백트래킹(Backtracking) 알고리즘은 결정 문제(예/아니오로 답할 수 있는 문제)를 해결하기 위해 사용되는 알고리즘 방법론이다. 백트래킹은 모든 가능한 경우의 수를 시스템적으로 탐색하여 문제의 해답을 찾습니다. 이 방법은 주로 조합 문제, 순열 문제, 분할 가능 문제 등에 사용된다.

 

백트래킹 알고리즘의 핵심 개념과 특징은 다음과 같다.

1. 재귀적 구조: 백트래킹은 재귀적으로 문제를 해결한다. 각 단계에서 가능한 모든 옵션을 시도하고, 그 중 하나를 선택하여 다음 단계로 넘어간다.

2. 탐색 범위 축소: 가능한 해가 될 수 없는 경우는 빠르게 배제함으로써 탐색 범위를 축소한다. 이를 통해 시간을 절약할 수 있다.

3. 해결책의 완성: 해결책을 단계별로 구축하다가 해결책의 조건을 만족하면, 그 해결책을 반환한다.

4. 백트래킹(되돌아가기): 현재 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 되돌아가서 다른 경로르 시도한다. 이 과정을 '백트래킹'이라고 한다.

5. 가지치기(Prning): 백트래킹은 '가지치기'를 통해 불필요한 경로를 조기에 배제한다. 즉, 현재 선택이 향후에 유망하지 않다고 판단되면, 그 선택을 포기하고 다른 선택을 시도한다.

 

백트래킹은 계산 복잡도가 높은 문제에 대해 상대적으로 효율적인 해결책을 제공하지만, 최악의 경우에는 모든 가능한 조합을 탐색해야 하는 단점이 존재한다.

 

 

 

---

 

 

 

문제 풀이:

체스에서의 퀸(Queen)은 2가지 방식으로 움직인다. 

1. 상하로 칸수와 상관없이 움직인다.

2. 대각선(좌우 상관x)으로 칸수와 상관없이 움직인다.

 

즉, 상하좌우대각선을 피하는 위치에 모든 퀸들이 존재해야한다.

 

첫째, 주어진 n값을 기준으로 N x N의 보드판을 생성해준다.

둘째, backtrack함수에서는 column의 크기만큼 반복을 진행해준다. 단, isValid함수를 사용하여 true 값일경우 'Q'값을 할당해주면서 그 다음 row 행을 탐색하는 재귀방식을 채택하였다.

셋째, 재귀와 포문을 반복하면서 row 와 board의 길이가 똑같아진다면 N x N 자리의 보드판에 모든 퀸이 놓아진것이기 때문에 soultionList 배열에 넣어준다.

 

 

자바스크립트 풀이:

function nQueen(n) {
  const board = new Array(n).fill().map(() => new Array(n).fill("."));
  const solutionList = [];
 
  backtrack(board, 0, solutionList);
 
  return solutionList;
}
 
function backtrack(board, row, solutionList) {
  if (row === board.length) {
    const solution = board.map((v) => [...v]);
    solutionList.push(solution);
    return;
  }
 
  for (let col = 0; col < board.length; ++col) {
    if (isValid(board, row, col)) {
      board[row][col] = "Q";
      backtrack(board, row + 1, solutionList);
      board[row][col] = ".";
    }
  }
}
 
function isValid(board, row, col) {
  for (let i = 0; i < row; ++i) {
    if (board[i][col] === "Q") {
      return false;
    }
  }
 
  for (let i = row, j = col; i >= 0 && j >= 0; --i, --j) {
    if (board[i][j] === "Q") {
      return false;
    }
  }
 
  for (let i = row, j = col; i >= 0 && j < board.length; --i, ++j) {
    if (board[i][j] === "Q") {
      return false;
    }
  }
 
  return true;
}

 

 

파이썬 풀이:

def n_queen(n):
 
    def in_valid(row, col):
 
        for i in range(0, row):
            if board[i][col] == 'Q':
                return False
 
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j] == 'Q':
                return False
 
        for i, j in zip(range(row, -1, -1), range(col, n, 1)):
            if board[i][j] == 'Q':
                return False
 
        return True
 
    def backtrack(row):
        if row == n:
            solution = [arr[:] for arr in board]
            solutionList.append(solution)
            return
 
        for col in range(n):
            if in_valid(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
 
    board = [['.' for _ in range(n)] for _ in range(n)]
    solutionList = []
    backtrack(0)
 
    return solutionList