IM 18일차 (Back Tracking)

1. Back Tracking

 

  DFS 방식으로 자료를 탐색할 때 유망하지 않은 것에 대해선 가지치기를 수행하여 이전으로 돌아가 재탐색하는 방식을 말한다.

  여기서 유망하다는 것의 의미는 '답이 될 수 있는 경로'를 의미한다.

  또한 가지치기란 유망하지 않은 것을 '잘라내다'라고 이해하면 된다.

 

 

 

2. 백 트래킹이 왜 필요할까?

 

  기본적으로 DFS 방식은 주어진 모든 데이터를 순회하는 완전 탐색 기법이다.

  따라서 백 트래킹 없이 탐색한다면 굳이 답이 되지 않는 경우도 탐색을 해야 돼서 시간적인 낭비라고 할 수 있다.

 

 

 

3. 대표적인 예시

 

  nQueens 문제를 DFS 방식과 Back Tracking 방식을 통해 효율적으로 풀 수 있다.

  nQueens 는 n by n의 체스판에서 n개의 queen을 놓을 수 있는 모든 경우의 수를 찾는 문제다.

  queen은 거리에 상관없이 가로, 세로, 대각선에 위치한 다른 말들을 공격할 수 있다.

  따라서 그러한 경우에 해당되지 않는 모든 경우의 수를 세야만 하는 것이다.

 

  let solutionCount = 0;
  let board = new Board({ n });
  let boardArr = board.rows();
  
  let countNQueens = function (col) {
    if (board.hasAnyQueensConflicts()) {
      return;
    } // 체스판에서 queen의 충돌여부가 있으면 더 이상 재귀 호출이 이루어지지 않음
      // 즉 유망하지 않은 길에 대한 가지치기라고 볼 수 있음.
    if (col === boardArr.length) {
      solutionCount++;
      return;
    } // 탈출 조건 
    for (let i = 0; i < boardArr.length; i++) {
      board.togglePiece(i, col); // 말을 놓을 자리에 대해 좌표를 0 -> 1
      countNQueens(col + 1); // 재귀 호출
      board.togglePiece(i, col); // 0 -> 1로 만들었던 좌표를 다시 1 -> 0 으로 만들어야 함.
    } 
  }
  countNQueens(0);
  return solutionCount;