1. 백트래킹 (Backtracking, 되추적) 방법
ㅇ 문제 풀이의 막다른 곳에 다다르면, 호출한 함수로 되돌려 나아가는 방법
- 앞쪽에 더이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법
- 문제를 푸는 과정 중 발생할 수 있는 모든 가능한 상태를 상태 공간 트리로써 구축함
- 주로, 깊이우선탐색(Depth First Search) 알고리즘을 이용하여 해답을 찾게됨
ㅇ 특징
- 해를 구할 때까지 모든 가능성을 시도하게 됨
. 갈 수 있는데까지 가보다가 막히면, (더이상 찾던 해가 없으면)
. 되돌아와서 다른 길을 찾아봄
- 되추적을 통해 탐색 대상을 줄여나감
. 되추적이 발생하면, 해당 서브트리들은 탐색대상에서 제외됨
- 주로, 그래프(상태 공간 트리)에 대해,
. DFS(깊이우선탐색)으로 탐색하며, (트리 순회)
. 재귀적으로 구현됨
- 문제가 커질 경우 엄청난 시간이 걸리므로,
. 분기한정법(Branch-and-Bound) 등 탐색 범위를 줄이는 여러 보완을 취함
ㅇ 탐색 방법
- (과정 1) 루트 노드를 현 위치 노드로 지정
- (과정 2) 현 위치 노드의 각 자식 노드에 대해 아래의 과정을 진행
. 해당 자식 노드 방향에 해가 있는지 확인
.. 해가 없다면,
... (과정 2)로 되돌아가서 진행
.. 해가 있다면,
... 해를 출력 또는 저장
... 하나의 해 만 구하는 문제인 경우에는 탐색 종료
. 자식 노드를 현 위치 노드로 지정하고, (과정 2)로 감 (깊이우선탐색)
- (과정 3) 부모 노드를 현 위치 노드로 지정한 후, 다음 자식 노드에 대해 (과정 2) 진행
ㅇ 적용 例) 미로 찾기 문제, 색칠 문제, 최적화 문제, 판정 문제 등