백트래킹 (Backtracking)

백트래킹(Backtracking)

---

 

조합, 순열, 그래프 탐색, 퍼즐 해결 등에 사용되는 자료구조이다.

"부분해"를 탐색하다가 문제가 발생하면 다시 돌아가서 다른 경로를 시도한다.

이 방식은 깊이 우선 탐색(Depth-First Search)과 비슷하지만, 특정 조건이 만족되지 않을 때 그 경로를 포기하고

이전 상태로 되돌아가서 다른 경로를 탐색하는 차이점이 있다.

 

백트래킹과 깊이 우선 탐색 (DFS)의 차이점

 

특징	백트래킹	깊이 우선 탐색 (DFS)
목표	주어진 문제의 해결책을 찾기 위해 가능한 모든 부분해를 탐색한다 조건을 만족하지 않으면 되돌아가서 다른 선택을 시도	그래프나 트리의 모든 노드를 탐색하여 목표 노드나 조건을 만족하는 노드를 찾는다
사용 목적	조합, 순열, 퍼즐 문제 등에서 가능한 해를 찾기 위해 사용한다	경로 찾기, 사이클 검출, 연결성 확인 등 그래프 탐색에 사용한다
탐색 방식	현재 단계에서 선택을 시도하고 유효하지 않으면 이전 단계로 돌아가서 다른 선택을 시도한다	노드를 깊이 우선으로 탐색하고,모든 자식 노드를 탐색한 후 부모 노드로 돌아온다
경로 검토	각 단계에서 유효성 검사를 통해 유효한 경로만 탐색하며 유효하지 않은 경로는 가지치기하여 탐색하지 않는다	그래프의 모든 경로를 탐색하며, 특정 노드를 찾거나 경로를 탐색한다
구현 방식	재귀 호출로 구현되며 현재 상태에서 가능한 모든 선택을 시도한다	스택을 사용하거나 재귀 호출을 통해 구현되며 모든 자식 노드를 깊이 탐색한 후 돌아온다

부분해

전체 문제가 완성된 해답에 도달하기 위해 반복적으로 작업을 수행하는 중간 결과이다.

백트래킹의 작동방식

1. 경로 선택: 문제를 해결하기 위해 가능한 선택을 하나씩 시도한다
2. 유효성 검사: 현재 선택이 문제의 조건을 만족하는지 확인한다
3. 해 결정을 위한 재귀 호출: 선택이 유효하다면, 그 선택을 기반으로 다음 단계로 진행한다
4. 백트래킹: 만약 현재 경로가 해결책이 아니라면, 선택을 취소하고 이전 상태로 돌아가서 다른 경로를 탐색한다

장점과 단점

• 장점: 백트래킹은 해를 찾는 과정에서 불필요한 탐색을 줄일 수 있다
• 단점: 문제의 크기가 커지면 탐색 공간이 급격히 증가하여 시간 복잡도가 높아질 수 있다.
• 따라서 효율적으로 탐색을 줄이기 위해 추가적인 최적화나 가지치기 기법이 필요할 수 있다