N-Queens Problem
N-Queens Problem은 NxN의 체스판에 N개의 퀸을 서로 충돌하지 않게 놓는 방법 혹은 그 경우의 수를 구하는 문제이다. 이 문제에서는 DFS와 백트래킹을 활용하여 필요없는 노드는 탐색하지 않도록 설정함으로써 탐색 효율을 높일 수 있다.
이미지 출처: codestates
위 그림과 같이 4X4 체스판의 경우는 4개의 퀸이 서로 충돌하지 않는 경우의 수를 찾아야 한다. 이번 스프린트는 페어 시간 이외에 검색도 많이 하고, 강의도 여러 번 돌려보고, 다른 동기들이 구현한 코드와 논리를 참고하여 완성하였다. 사실 다시 해보라고 하면 100% 완벽히 구현할 수 있을지 잘 모르겠지만, 코드를 구현하는 과정에서 백트래킹의 개념을 좀 더 명확히 이해할 수 있었고, 재귀와 함수 스코프(scope)에 대해서도 다시 한 번 공부해 볼 수 있었다는 점에서 얻은 게 많았다. 개인적으로 알고리즘 논리를 만들어가는 과정이 어렵지만 재밌었다.
깊이 우선 탐색(DFS)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉 노드가 자식을 가지고 있다면 그 노드의 깊이를 모두 탐색한 후, 다음 분기로 넘어간다. 너비 우선 탐색(BFS)에 비해 좀 더 간단하며 메모리를 적게 차지한다. 그러나 DFS는 모든 경로를 탐색하기 때문에 불필요한 경로를 탐색하지 않게 할 수 없어 답을 찾기 위한 경우의 수를 줄일 수 없다.
백트래킹(Backtracking)
백트래킹(Backtracking)은 답을 찾는 과정에서 현재의 경로가 답이 될 수 없다고 판단되면 그 경로의 탐색을 중단하고 다른 경로를 찾아가는 방식을 말한다. DFS는 모든 노드를 탐색하는 방법이지만, 백트래킹은 특정 조건을 설정하여 답이 될 수 없는 노드는 탐색하지 않기 때문에 이를 활용하면 탐색 효율을 높일 수 있고 답을 찾기 위한 경우의 수를 줄일 수 있다 즉 백트래킹으로 답이 될 수 없는 상황을 설정하고, 그러한 상황에서의 탐색을 중단시킨 뒤 그 이전으로 돌아가서 다른 경우를 탐색하게 구현할 수 있다. N-Queens에서는 충돌이 있으면 놓았던 말을 제거하고, 충돌이 없으면 다음 행으로 이동하여 다시 경우의 수를 탐색하도록 구현한 것이 백트래킹을 활용한 부분이다.
재귀(Recursion)
어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 한다. 코드 구현 시 실행과정 중에 자기 자신을 호출하기도 하는데 이러한 호출 방식을 재귀 호출이라고 한다. 재귀는 아래와 같은 상황에 매우 적합하다.
- 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
- 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우
모든 재귀 함수는 재귀 호출 없이 반복문(while / for loop)으로 표현할 수 있지만, 재귀가 사용 가능한 경우, 재귀를 사용한 코드가 대부분 더욱 간결하고, 일부는 이해하기도 쉽다. DFS는 대표적으로 재귀 호출을 통해 구현되므로 N-Queens에서도 재귀를 사용하였고, 충돌없이 마지막 행에 도달했을 때 보드를 반환하는 것을 탈출 조건으로 설정하여 재귀함수를 구현하였다.
JS 코드 구현
n이 2나 3인 경우, nxn 보드에 n개의 퀸을 다 놓을 수 있는 경우의 수가 0이므로 예외처리하였다.
1) n이 2인 경우(2X2보드에 2개의 퀸을 다 놓을 수 없음)
이미지 출처: 필자 제작
2) n이 3인 경우(3X3보드에 3개의 퀸을 다 놓을 수 없음)
이미지 출처: 필자 제작
window.findNQueensSolution = function (n) {
let board = new Board({ n: n });
let solution = board.rows();
if (n === 2 || n === 3) {
return solution;
}
function findNQueens(row) {
if (row === n && !board.hasAnyQueensConflicts()) {
return board.rows();
} //충돌없이 마지막 행에 도달했을 때 보드 반환(탈출 조건)
for (let col = 0; col < n; col++) {
board.togglePiece(row, col); // 전체 보드에 말 놓음
if (!board.hasAnyQueensConflicts()) {
solution = findNQueens(row + 1); //충돌이 없으면 다음 행으로 이동(백트래킹)
if (solution !== undefined) {
return solution; // 해답이 있으면 해답 반환
}
}
board.togglePiece(row, col); //충돌이 있으면 말 제거
}
}
findNQueens(0); //재귀함수 실행
}