백트래킹

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

DFS와 백트래킹

깊이 우선 탐색 (DFS)

DFS는 가능한 모든 경로를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄일 수 없다. 따라서 N!가지의 경우의 수를 가진 문제를 DFS로 처리하긴 힘들다.

백트래킹 (backtracking)

해를 찾는가는 도중 지금의 경로가 해가 되지 않을거 같으면 더이상 진행하지 않고 되돌아 간다.
즉, 반복문의 횟수를 줄일 수 있으므로 효율적으로 사용가능하다.
이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 옳바른 쪽으로 간다는 의미이다.
정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다! 즉, 답이 될만한 가능성이 없으면 더 이상 탐색을 진행하지 않고 가지치기를 하면서 최적해를 구하는 것이다.

백트래킹의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드 (부모)로 돌아가 (Backtracking) 다음 자식 노드로 이동한다.

해가 될 만한 가능성이 있으면 유망하다 (promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기 (pruning)라고 한다.

백트래킹의 대표적인 예제인 nQueen코드로 이해해보자

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class nQueen {
   static int N;
   static int[] board;
   static int count = 0;

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       N = Integer.parseInt(br.readLine());
       board = new int[N];

       nQueen(0);
       System.out.println(count);
   }

   static void nQueen(int depth){
       if(depth == N){
           count++;
           return;
       }
       for(int i = 0; i < N; i++){
           board[depth] = i;
           if(possible(depth)){
               nQueen(depth+1);
           }
       }
   }

   static boolean possible(int n){
       for(int i = 0; i < n; i++){
           if(board[n] == board[i]){
               return false;
           }
           else if(Math.abs(n-i) == Math.abs(board[n] - board[i])){
               return false;
           }
       }
       return true;
   }

}