[알고리즘] Backtracking(백트래킹)

재귀함수를 좀 더 빨리 돌려보자

백트래킹

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법.
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.
• 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.
• 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미.
• 실제 구현 시 고려할 수 있는 모든 경우의 수를 상태 공간트리(State Space Tree) 를 통해 표현.
  • 상태 공간 트리 : 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리
  • 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될 만한 곳으로 바로 넘어가서 탐색

백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

사용 예시 1. 피보나치 수열

public static Integer[] database;
    //int[]  0 0 0 0 0
    //Integer[] null null null null null

    public static int fibonacci2(int index) {//6
        if (database[index] != null){
            return database[index];
        }

        //database[3] = 2;
        //database[2] = 1;
        //database[4] = 3;
        int value = fibonacci2(index - 1) + fibonacci2(index - 2);
        database[index] = value;


        return value;
    }

• 같은 문제를 풀어도 재귀함수를 사용할 때 보다 백트래킹을 사용했을 때 시간이 단축되는 것을 경험할 수 있다.
• 무조건 0이나 1로 돌아가 문제를 푸는 재귀함수에 비해, 백트래킹은 각 값을 미리 저장해놓고 다시 돌아가지 않기 때문에 빠르다.

DFS와 백트래킹(Backtracking)의 차이

• DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기에 재귀 또는 스택을 이용한다.
• 재귀를 이용하여 탐색을 수행한다는 부분에서 완전탐색 알고리즘의 재귀 / 백트래킹(Backtracking)과 유사한 측면이 보여 혼란이 올 수 있다.
• 그런데, 재귀라는 것은 말 그대로 스스로의 함수(또는 메소드)를 호출하는 방식을 의미하는 것이므로 DFS가 재귀라는 방식을 이용해 탐색을 수행하는 것으로 하나의 방식이라고 이해하면 된다.
• 또한, 백트래킹(Backtracking)은 재귀를 통해 알고리즘을 풀어 가는 기법 중 하나로 가지치기(Pruning)을 통해서 탐색을 시도하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.
• DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만 상황에 따라서 백트래킹 기법을 혼용하여 불 필요한 탐색을 그만두는 것이 가능하다.

  즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다.
  완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.

출처 : https://hongjw1938.tistory.com/88