깊이 우선 탐색(Depth-First Search)와 되추적(Backtracking)을 활용한 Nqueens 문제해결
1. 너비 우선 탐색(Breadth-first search)
루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 현재 탐색할 레벨에 있는 노드를 모두 방문한 뒤에 다음 레벨에 있는 노드를 탐색한다. 아래 트리를 탐색하는 순서는 root, 1, 2, 3, 4, 5, 6이다.
너비 우선 탐색은 깊이 탐색하기 전에 넓게 탐색한다. 주로 두 노드 사이의 최단경로나 임의의 경로를 찾아야 할 때 사용한다. 이를 구현하려면 현재 레벨에서 방문해야 할 노드를 차례로 저장하고, 꺼낼 수 있는 큐(Queue)를 사용해야 한다.
2. 1. 깊이 우선 탐색(Depth-first search)
루트 노드에서 시작하여 다음 인접노드로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 넓게 탐색하기 전에 깊이 탐색하는 방법. 주로 모든 노드를 방문해야할 경우에 사용한다. 위 트리에서 노드를 방문하는 순서는 root, 1, 3, 4, 2, 5, 6이다.
2. 2. 되추적(Backtracking)
깊이 우선 탐색은 자료의 크기가 방대해질 경우 시간복잡도가 기하급수적으로 커지게 된다. 따라서 모든 노드를 방문하기보다, 방문할 노드의 유망성(Promosing)을 확인하고, 유망하지 않으면 해당 노드를 방문하지 않고 부모노드로 돌아가서 다른 자손노드를 탐색한다. 이를 가지치기(Pruning)라고 한다.
깊이 우선 탐색과 되추적은 재귀호출과 스택 자료구조를 활용하여 구현할 수 있다. 예제에서는 클래스와 재귀호출 방식을 사용하였다.
3. NQueens 문제해결
N-queens 문제에서 깊이 우선 탐색을 재귀호출로 구현하면서 보드 matrix가 제대로 구현되지 않는 문제가 발생했다. 매 탐색마다 보드판에 말을 놓고, 탐색한 뒤에 해당 말을 원위치하는 백트래킹을 제대로 구현하지 못해 발생한 문제였다.
알고리즘을 해결하는 함수는 보드판 인스턴스와 nQueens를 해결하는 재귀함수를 내부에 변수로 저장하고 있었다. 재귀함수는 자신의 스코프에 보드판 Matrix를 변수로 가지고 있지 않으니, 외부 스코프에서 이를 호출한다. 이 과정에서 문제가 발생했다. 동일한 보드판 인스턴스를 여러 재귀함수 콜스택에서 호출하다보니, 이전 콜스택에서 말을 놓고나면 그 위치에 그대로 있었다. 노드상으로 동일한 레벨의 다음 콜스택이 호출했을 때, 보드판의 배치가 이전 시행과는 달라게 된 것이다. 당연히 제대로 탐색이 되지 않았다. 그 결과 1번째 열의 모든 칸에 말이 놓이고 다음 단계로 넘어가지 않았다.
해결 방법은 생각보다 간단하다. 다음 탐색을 진행하기 전에 현재 보드의 상태를 원상복귀해주면 된다. 덕분에 백트래킹 개념을 머리 속에 확실히 각인시켰다.
// #1. 개인풀이
function countNQueensSolutions(n) {
const matrix = new Board({n: n});
let answer = 0;
function solution(rows) {
if ( rows === n) {
answer ++;
return;
}
for (let i = 0; i < n; i++ ) {
matrix.togglePiece(rows, i);
if (!matrix.hasAnyQueenConflictsOn(rows, i)) solution(rows + 1);
matrix.togglePiece(rows, i); // Backtracking
}
}
solution(0);
return answer;
}
// #2. 레퍼런스 코드
function searchWtRecursion(row, n, board, hasConflict, callback) {
if (row === n) return callback();
for (let col = 0, col < n; col++) {
board.togglePiece(row, col);
if (!hasConflict()) {
const result = searchWtRecursion(row + 1, n, board, hasConflict, callback);
if (result) return true;
}
board.togglePiece(row, col);
}
return false;
}
function countNQueensSolutions(n) {
const board = new Board({n: n});
const hasConflict = board['hasAnyQueensConflicts'].bind(board);
let count = 0;
searchWtRecursion(0, n, board, hasConflict, function() {
count++;
return false;
})
return count;
}
function findNqueensSolution(n) {
const board = new Board({n: n});
const hasConflict = board['hasAnyQueensConflicts'].bind(board);
searchWtRecursion(0, n, board, hasConflict, function() {
return true;
})
const solution = board.rows();
return solution;
}
스프린트에서는 이차원 배열로 매트릭스를 구현하여 문제를 풀었지만, 1차원 배열로도 충분히 문제를 해결할 수 있다. 4 x 4 체스판을 만든다고 해보자. 이를 1차원, 2차원 배열로 각각 다음과 같이 만들 수 있다. 이 방법은 각 열에 말을 하나씩만 둘 수 있는 상황에만 사용할 수 있다.
// 2차원 배열로 구현한 NQueens 보드판
[
[0, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]
]
// 1차원 배열로 구현한 NQueens 보드판
[1, 0, 2, 3]
퀸은 좌우상하와 대각선 방향으로 움직일 수 있다. 각 열에는 무조건 하나의 말 밖에 둘 수 없다는 것을 알아두자. 따라서, 1차원 배열에서 요소의 값(value)는 x축 좌표를 나타내고, 인덱스(index)는 y축 좌표를 나타내도록 표현할 수 있다.
그 다음으로 퀸들 사이에 충돌이 있는지 확인해야 한다. 좌우 방향은 각 열에 하나만 두도록 배열을 만들었으므로 해결되었다. 상하 방향에 간섭되는 말이 있는지 확인하려면, 배열 내에 동일한 값을 가진 요소가 2개 이상 있는지 확인하면 된다. 값(value)이 x축 좌표이기 때문이다.
대각선 방향은 어떻게 확인할 수 있을까. 앞서 언급했듯이 퀸은 대각선 방향으로 움직일 수 있는데, 기울기($y/x$)가 $1$ 또는 $-1$ 이라는 것에 주목하자. 좌표계에서 동일 직선상에 위치한 좌표들의 기울기는 모두 동일하다. 따라서 ${\Delta}y/{\Delta}x$의 절댓값이 $1$인지만 확인하면 되는 것이다. 풀이는 다음과 같다.
// #1. 개인풀이
function solution(n) {
let answer = 0;
let isPruning = false;
const board = [];
function nqueen(i) {
// 탈출조건에 도달하면 종료한다.
if ( i === n ) {
answer ++;
return;
}
// 해당 열에 좌표값을 넣고 확인한다.
for ( let j = 0; j < n; j++ ) {
board[i] = j;
for ( let k = 0; k < i; k++ ) {
if ( j === board[k] || (Math.abs(j - board[k]) === Math.abs(i - k)) ) isPruning = true;
}
if ( !isPruning ) nqueen(i + 1);
isPruning = false;
board[i] = 0;
}
}
nqueen(0);
return answer;
}
// #2. 레퍼런스 코드: 대칭을 활용하여 연산속도를 훨씬 단축시켰다.
function solution(n) {
const colUsed = Array(n).fill(false);
const slashUsed = Array(2 * n + 1).fill(false);
const backSlashUsed = Array(2 * n + 1).fill(false);
const isValid = (r, c) =>
!(colUsed[c] || slashUsed[r + c] || backSlashUsed[c - r + n]);
const place = (r, c) =>
(colUsed[c] = slashUsed[r + c] = backSlashUsed[c - r + n] = true);
const unPlace = (r, c) =>
(colUsed[c] = slashUsed[r + c] = backSlashUsed[c - r + n] = false);
const aux = (row) => {
if (row === n) return 1;
let cnt = 0;
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
place(row, col);
cnt += aux(row + 1);
unPlace(row, col);
}
}
return cnt;
};
let cnt = 0;
for (let i = 0; i < Math.floor(n / 2); i++) {
place(0, i);
cnt += aux(1);
unPlace(0, i);
}
cnt = 2 * cnt;
if (n % 2 === 1) {
place(0, Math.floor(n / 2));
cnt += aux(1);
}
return cnt;
}
Leave a comment