백트래킹(BackTracking) 이란?
가능한 모든 후보해를 탐색하면서 해결책을 찾는 알고리즘 기법.
일반적으로 깊이 우선 탐색(DFS) 를 기반으로 하며, 모든 가능성을 탐색하다가 현재 경로가 해결책으로 이어질 수 없는 경우, 그 경로를 포기하고 이전 상태로 돌아가 다른 경로를 탐색
백트래킹의 주요 개념
- 상태 공간 트리 (State Space Tree)
- 문제의 가능한 해결책을 나타내는 트리 구조
- 각 노드는 문제 상태를 나타내며, 간선은 한 상태에서 다음 상태로의 전이를 나타냄
- 제약 조건(Constraints)
- 문제의 해결책이 되기 위해 만족해야 하는 조건
- 백트래킹에서는 이러한 제약 조건을 만족하지 않는 상태는 탐색하지 않음
- 가지치기 (Pruning)
- 탐색 과정 중에 유망하지 않은 노드를 미리 제거하여 탐색 시간을 단축하는 기법
- 가지치기는 유망성 검사를 통해 이루어짐
- 재귀적 접근(Recursive Approach)
- 백트래킹 알고리즘은 보통 재귀적으로 구현됨
- 한 상태에서 다음 상태를 탐색하고, 만약 해결책으로 이어지지 않으면 이전 상태로 되돌아가 다른 후보를 탐색
백트래킹의 알고리즘 단계
- 선택 (Choose)
- 현재 상태에서 다음 상태로 진행할 선택을 만듬
- 조건 검사 (Constraint)
- 선택한 후보가 제약 조건을 만족하는지 확인
- 제약 조건을 만족하지 않으면 해당 후보는 버려짐
- 해결책 발견 (Goal)
- 선택한 후보가 해결책에 도달했는지 확인
- 해결책에 도달하면 결과를 출력하고 종료
- 재귀 호출 (Explore)
- 선택한 후보가 제약 조건을 만족하면 해당 후보를 다음 상태로 이동시키고 재귀적으로 탐색을 진행
-만약 해결책에 도달하지 못하면 이전 상태로 되돌아가 다른 후보를 탐색
- 복구 (Unchoose)
- 재귀 호출에서 돌아온 후에는 선택한 후보를 제거하고 이전 상태로 돌아감
백트래킹의 구현
백트래킹은 주로 재귀 함수를 통해 구현됨. 재귀 함수는 현재 상태에서 다음 상태로 진행하며, 만약 해결책에 도달하지 못하면 이전 상태로 돌아가는 방식으로 동작함. 여기에 유망성 검사를 통해 불필요한 탐색을 줄이고, 가지치기를 톻애 실행 속도를 향상
Hello World