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

백트래킹

재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다.

해를 찾는 도중에 막히면 해당 상태로 더 탐색하지 않고 돌아가서 해를 찾아나가는 방식이다.

이때 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다.

모든 경우의 수를 체크하지 않게 되므로 시간을 단축할 수 있다.

 

유사한 알고리즘으로 DFS(깊이 우선 탐색)이 있다.
DFS와 백트래킹의 차이는 DFS는 모든 경우의 수를 탐색하지만 백트래킹은 DFS와 다르게 백트래킹은 불필요한 탐색을 하지 않는다.

 

 

사용 문제

• 의사결정 문제
• 최적화 문제
• 열거 문제

 

 

핵심 아이디어

재귀 호출 : 문제를 해결하기 위해 재귀호출을 사용한다.

가지치기 : 불 필요한 경우의 수는 제외하고 탐색한다. 현재 상태에서 더 이상 원하는 해를 찾을 가능성이 없다면, 해당 상태를 더 이상 탐색하지 않고 돌아간다.

제약 조건 확인 : 현재 상태가 문제의 조건에 만족하는지 확인하고, 조건에 만족하지 않는다면 해당 상태를 제외하고 다음단계로 나아간다.

 

 

 

구현