프로그래밍으로 풀고자 하는 문제중에는 올바른 선택의 순열을 구하는 문제들이 있습니다. 이런 문제들은 모든 가능한 선택순서의 경우의 수를 탐색하는 무식하게 풀기 방법으로도 풀 수 있지만 조금 더 효율적으로 접근할 수도 있습니다. 바로 역추적이라는 방법입니다.
역추적은 선택을 계속 하면서 오류가 발생했을 때 틀린 선택을 하기 전의 선택으로 되돌아가서 다시 시작함으로써 잘못된 선택을 한 이후에 계속 선택을 해서 쓸모없는 반복탐색을 하지 않는 방법입니다.
예로 들수 있는 문제는 여덟 퀸 문제가 있습니다. 여덟 퀸 문제는 체스 판 위에 여덟 개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다.
이 문제를 역추적으로 어떻게 접근 할 수 있을까요?
문제를 먼저 파악해보면 여덟 퀸 문제는 첫번째 퀸 위치 선택, 두번째 퀸 위치 선택, 세번째 퀸 위치 선택,...,여덟번째 퀸 위치 선택까지 총 8개의 위치 선택을 순서대로 해야하는 문제입니다. 즉 선택의 올바른 순서를 구하면 되는 문제라는 것이고 역추적을 적용하기 알맞은 문제입니다.
반복전략을 사용하여 구해봅시다.
반복할 절차는 다음과 같습니다.
1. i번째 퀸을 다른퀸을 공격하지 않도록 배치합니다.
-이때 i번째 퀸이 반복전략을 하면서 다른 곳에 배치해서 탐색한 적이 있었다면 그 곳말고 다른 곳 에 배치를 한다.
2. 만일 i번째 퀸을 다른퀸을 공격하지 않도록 배치할 수 없다면 i=i-1로 바꾸어 반복절차를 다시 수행합니다.
탈줄 조건은 다음과 같습니다.
1. 8번째 퀸까지 배치를 완료하면 퀸들의 위치를 return하고 반복을 끝냅니다.
이 절차를 따라 javascript로 코딩해보겠습니다.
function queens8(board){ //arr은 첫번째 퀸의 위치를 이중배열에 담은 것. 첫번째 퀸을 arr위치에 두었을 때의 queens8문제의 답안을 리턴하는 함수
if(board.length===8){
return board;
}
const nextStep=position(board);
for(let i=0;i<nextStep.length;i++){
board.push(nextStep[i]);
solution = queens8(board);
if(Array.isArray(solution)){
return solution;
}
board.pop();
}
return false;
}
function position(solution){ //solution은 여러 퀸들의 위치를 이중 배열로 담은 것. 현재 퀸 배열을 입력했을 때 다음 퀸의 배치 가능한 보드 판 위치들을 리턴하는 함수.
const board=[];
for(let i=1;i<=8;i++){
let count=0;
for(let j=0;j<solution.length;j++){ //보드위 퀸에 대하여 가로축상 위치들을 다음 퀸이 들어갈 경우의 수에서 제거한다.
if(solution[j][0]===i){
count=1;
continue;
}
}
if(count===1){
continue;
}
for(let j=1;j<=8;j++){ //보드위 퀸들에 대하여 세로축상 위치들을 다음 퀸이 들어갈 경우의 수에서 제거한다.
for(let k=0;k<solution.length;k++){
if(solution[k][1]===j){
count=1;
continue;
}
}
if(count===1){
count=0;
continue;
}
for(let k=0;k<solution.length;k++){ //보드위 퀸들에 대하여 다이고널 위치들을 다음 퀸이 들어갈 경우의 수에서 제거한다.
if(digonalMaker(solution[k]).some(function(item) {
return (item[0] === i&&item[1]===j)
})){
count=1;
break;
};
}
if(count===0){
board.push([i,j]);
}else{
count=0;
}
}
}
return board;
}
function digonalMaker(arr){ //arr 임의의 퀸의 위치를 배열로 담은 것. 입력된 퀸의 위치에 대하여 대각선 위치들을 배열에 담아 리턴하는 함수
const digonal=[];
let rightD=arr[0]-arr[1], leftD=arr[0]+arr[1];
//오른쪽 대각선 요소들을 digonal에 담는다.
for(let i=1+rightD;i<=8;i++){ //자랑삼아 반복문의 수학적 모델을 적는다. 퀸의위치가 (m,n)일때 해당 퀸의 속한 rightdigonal은 m-n값에 따라 구분됨을 이용했다.
if(i>=1){
digonal.push([i,i-rightD]);
}
if((i-rightD)===8){
break;
}
}
for(let i=leftD-8;i<=8;i++){ //왼쪽 대각선 요소들을 digonal에 담는다.
if(i>=1){ //이 반복문의 수학적 모델을 적는다. 퀸의 위치가 (m,n)일때 leftdigonal은 m+n의 값에 따라 구분됨을 이용했다.
digonal.push([i,leftD-i]);
}
if((leftD-i)===1){
break;
}
}
return digonal;
}