Backtracking

• 백트랙킹
  • 탐색 도중 조건에 맞는 경로만 찾고, 조건에 맞지 않는 경로는 탐색하지 않고 돌아가는 것.
• 가지치기
  • 탐색 도중 조건에 맞지 않는 경로인 경우, 그 경로는 더 이상 탐색하지 않고 잘라내는 것.
• 정리하자면, 조건에 맞지 않는 경로는 가지치기를 하고 돌아가는 것을 백트랙킹 이라고 한다.

• Backtracking의 좋은점?
  • 탐색 효율이 말도 안되게 높아진다.
  • 모든 노드를 탐색할 필요없이 조건에 맞는 노드만 탐색하면 되므로 데이터가 많아질수록 효율성이 극대화된다.

---

N-Queens를 구현하면서 백트랙킹과 재귀에 대해 좀 더 알아보겠다.

  let board = new Board({n:n}); //n * n의 체스판을 생성
  let rowIdx = 0; // 체스판의 행
   
  function recursion (rowIdx, board) { //0, board
    if (rowIdx === n) { //n은 행의 길이, ex) n === 4
      return true;
    } //행이 체스판 끝?에 도달했을 때 

    for (let i = 0; i < n; i++) {
        board.togglePiece(rowIdx, i); //(0, i) => ex) 0번째 행 + i번째 열  -> 0,0
        if (board.hasAnyQueenConflictsOn(rowIdx, i)) { //0번째 열의 충돌 유무
          board.togglePiece(rowIdx, i); //충돌 ! => rook 제거
          continue; // 가지치기
        } else { //충돌이 발생하지 않으면
          let result = recursion(rowIdx + 1, board); // 다음 행으로 넘어가라 
          //board.togglePiece(rowNum, i);
          if (result === false) {
            board.togglePiece(rowIdx, i);
          } 
          if (result === true) {
            return;
          }
        } 
    } 
    return false;
  }
  
  recursion(rowIdx, board); 
  const solution = board.rows(); //board.rows(); // fixme

  console.log(
    'Single solution for ' + n + ' queens:',
    JSON.stringify(solution)
  );
  return solution;

위 코드에서 continue 부분은 충돌이 발생한 경우 두었던 퀸을 제거하고 else를 뛰어 넘은 후 반복문으로 돌아간다. 즉, 충돌이 발생한 <행, 열> 은 더 이상 보지 않고 넘어가기 때문에 가지치기 이후 백트랙킹 한다는 걸 알 수 있다.

추가적으로 recursion() 의 과정을 살펴본다.

1. <4,4> 체스판을 가정하고 recursion(rowIdx, board) 호출

1 0 0 0 => <0,0>에 퀸이 자리 잡는다.
0 0 0 0
0 0 0 0
0 0 0 0

2. <0,0> 에서 충돌이 발생하지 않으므로 recursion(rowIdx + 1, board) 재귀 호출

1 0 0 0
0 0 1 0
0 0 0 0
0 0 0 0

3. <1,2> 에서 충돌이 발생하지 않으므로 recursion(rowIdx + 1, board) 재귀 호출

1 0 0 0
0 0 1 0
x x x x => 3번째 행에서 충돌이 발생하지 않는 좌표는 없다. 따라서 for loop이 다 끝나고 return false
0 0 0 0

4. 2번으로 다시 돌아와 재귀 호출한 recursion(rowIdx + 1, board) 함수가 false값을 가지고 돌아온다. 위 코드에서 false값을 받아오면 해당 좌표의 퀸은 다시 삭제를 해준다. 그리고 2번째 행에서 돌고 있던 for loop을 다시 돌기 시작해서 <1,3>에 퀸을 다시 놓는다.

1 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0

5. <1,3> 은 충돌이 발생하지 않으므로 recursion(rowIdx + 1, board) 재귀 호출. <2,1>에 퀸을 놓을 수 있으므로 놓고 다시 recursion(rowIdx + 1, board) 재귀 호출

1 0 0 0
0 0 0 1
0 1 0 0
0 0 0 0

6. 3번째 행은 퀸을 놓을 자리가 없다. 따라서 for loop을 다 돌고 return false

1 0 0 0
0 0 0 1
0 1 0 0
x x x x

7. false값을 5번에 재귀 호출한 자리로 돌아간다. 리턴값이 false이므로 해당 좌표에 퀸을 삭제하고 반복문을 다시 돌린다. 하지만 3번째 행에는 더 이상 퀸을 놓을 자리가 없기 떄문에 return false

1 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0

8. 4번으로 돌아가 2번째 행에서 돌고 있던 반복문의 recursion 함수로 돌아간다. 하지만 여기서도 false값을 갖고 왔기 때문에 <1,3>의 퀸을 제거한다. 그리고 반복문도 다 돌았기 때문에 return false

9. 2번으로 돌아가 해당 좌표의 퀸을 제거하고 다시 반복문을 돌린다. 여기서의 반복문은 처음으로 돌아와 첫 번째 행의 퀸의 자리를 탐색하는 반복문이다.