TIL 50일차 - N-Queens 알고리즘과 다른 알고리즘
사고력을 기르는 중입니다.
Today’s Key 🔑
- 아침에 코플릿 알고리즘 문제를 풀면서 너무 닫혀있는 내 사고에 답답함을 느끼고, 계속해서 다른 문제를 번갈아 가면서 풀었다.
- 새롭게 시작된 n-queens 알고리즘 스프린트는 상당히 머리를 어지럽게 만들었다.
- 본격적인 스프린트 시작 전 3명의 페어들과 팀을 짜서 n-queens 문제에 대한 전략을 세워보는 시간을 가졌다. 새로운 방식이었다.
- n-queens의 queens-n-count 코드를 정리해보고자 한다.
N x N 칸의 체스판에 퀸을 서로 공격 못하게 배치하자.
우리가 구현해야 하는 N-Queens 알고리즘은 이중 배열을 기반으로 탐색하고, 조건을 만족하는 (체스판에서 퀸이 서로 공격하지 않는) 모든 조합을 찾아야 한다.
탐색을 하기 위해서는 DFS와 백트래킹 이라는 탐색 방법을 알아야 했다.
BFS는 너비 우선 탐색의 약자이다. 트리나 그래프 자료구조의 depth, 즉 계층별로 탐색을 진행하는 완전 탐색 방법 중 하나이다. 시작점을 탐색하고, 아래에 계층이 있으면 순서대로 그 계층의 요소를 점검한다. 이렇게 한 계층의 탐색이 끝나면 그 다음 계층의 탐색으로 이어지는 탐색 방법이다.
DFS는 BFS와 정반대로 깊이를 우선적으로 탐색하는 방법이다. 시작점을 탐색하고, 아래에 요소가 있다면, 재귀를 돌려서 가장 아래의 요소까지 순차적으로 탐색하고, 다시 재귀의 콜스택을 거슬러 올라가 탐색을 진행한다. 재귀 처리의 끝판왕인 것 같다.
n-queens 알고리즘에는 백트래킹이라는 탐색 방법도 필요했다. DFSF를 진행하면서, 유망성이 있는 즉 다음을 탐색할 가치가 있는 것에 대해서만 다시 DFS 탐색으로 처리해주는 것이다. (으아 어려운 개념이다.) 간단하게 말해서, DFS를 진행하는 도중 특정 조건을 만나고, 그 조건을 충족할 때에만 다시 탐색을 진행하는 것이라고 생각하면 맘 편할 것 같다.
즉, DFS를 이용하여 탐색을 할 때, 특정 조건을 충족하지 못하면 재귀를 그 자리에서 리턴 시켜버리면 된다는 것이다. 민철님은 이런 처리를 할 때 보통적으로 사용하는 탬플릿이 있다고 설명해주었다. 각설하고 코드를 보자.
countNQueens = (n) => {
// 만족하는 조건을 찾으면 count += 1
let count = 0;
const board = new Board({ n: n }); // 미리 Board 클래스를 만들었다.
// 우리는 기본적으로 재귀를 이용해서 체스판을 반복 탐색할 것이다.
const recur = (row) => {
// 탈출 조건 1.
// queens 충돌이 없으면 재귀 콜스택 복귀
if (board.hasAnyQueensConflict()) return;
// 탈출 조건 2.
// 모든 행에 퀸 배치가 끝나면 한 조합이 완성된 것
if (row === n) {
count += 1;
return;
}
// 반복해서 퀸을 놓는다.
for (let col = 0; col < n; col += 1) {
// 우선 퀸을 놓는다.
board.togglePiece(row, col);
// 체스판을 검사하고, 리턴 받으면 아래에서 체스를 다시 땐다.
recur(row + 1);
board.togglePiece(row, col);
}
};
// (0,0) 좌표부터 재귀로 탐색한다.
recur(0);
return count;
};
빡세다.. 다시 정리하는 것에도 머리가 지끈하다.