Backtracking   백트래킹, 되추적 기법

1. 백트래킹 (Backtracking, 되추적) 방법

  ㅇ 문제 풀이의 막다른 곳에 다다르면, 호출한 함수로 되돌려 나아가는 방법 
     - 앞쪽에 더이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법
     - 문제를 푸는 과정 중 발생할 수 있는 모든 가능한 상태를 상태 공간 트리로써 구축함
     - 주로, 깊이우선탐색(Depth First Search) 알고리즘을 이용하여 해답을 찾게됨

  ㅇ 특징
     - 해를 구할 때까지 모든 가능성을 시도하게 됨
        . 갈 수 있는데까지 가보다가 막히면, (더이상 찾던 해가 없으면)
        . 되돌아와서 다른 길을 찾아봄
     - 되추적을 통해 탐색 대상을 줄여나감
        . 되추적이 발생하면, 해당 서브트리들은 탐색대상에서 제외됨
     - 주로, 그래프(상태 공간 트리)에 대해,
        . DFS(깊이우선탐색)으로 탐색하며, (트리 순회)
        . 재귀적으로 구현됨
     - 문제가 커질 경우 엄청난 시간이 걸리므로, 
        . 분기한정법(Branch-and-Bound) 등 탐색 범위를 줄이는 여러 보완을 취함

  ㅇ 탐색 방법
     - (과정 1) 루트 노드를 현 위치 노드로 지정
     - (과정 2) 현 위치 노드의 각 자식 노드에 대해 아래의 과정을 진행
        . 해당 자식 노드 방향에 해가 있는지 확인
           .. 해가 없다면, 
               ... (과정 2)로 되돌아가서 진행
           .. 해가 있다면,  
               ... 해를 출력 또는 저장
               ... 하나의 해 만 구하는 문제인 경우에는 탐색 종료
        . 자식 노드를 현 위치 노드로 지정하고, (과정 2)로 감  (깊이우선탐색)
     - (과정 3) 부모 노드를 현 위치 노드로 지정한 후, 다음 자식 노드에 대해 (과정 2) 진행

  ㅇ 적용 例) 미로 찾기 문제, 색칠 문제, 최적화 문제, 판정 문제 등