.jpg&blockId=1b87074d-017e-8069-9667-d5678d39e51d)
기본적인 아이디어
•
해를 찾는 도중 해가 아니어서 막히면, 되돌아 가서 다시 해를 찾아가는 기법
•
DFS(깊이 우선 탐색) → 모든 가능한 경로를 탐색한다.
•
DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어, 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색한다.
기본적인 형식
1. 기본적으로 재귀를 사용한다.
2. 재귀 상에서 항상 접근가능한 어떤 공간을 형성해놓는다.
3. 함수를 호출할 때는 종료 조건이 있으며, 그 다음 단계로 이동하는 코드가 존재한다.
따라서
void back_track(int n, int m, int cnt){
//종료조건
if(cnt == m){
}
// 그 다음 조건을 탐색하는 조건
for(int i=1; i<=n; i++){
//cnt -> 지금 접근하고 있는 깊이를 나타냄
if(next_condition == possible){
// 조작
back_track();
// 조작 취소
}
else pass;
}
}
JavaScript
복사
N과 M(1)
백트래킹 대표 예제
이걸 보면서 어떻게 백트래킹을 해야할지 생각해보자
N과 M(2)
N과 M(3)
N과 M(4)
N-Queen
백트래킹 대표 어려운 예제
백트래킹을 할 때, 순환을 어떻게 하면 될지를 생각하게 해주는 문제
백트래킹할 때 중요한 것
1.
어떤 걸 기준으로 순환을 할 거냐
2.
순환을 하면서 가능한 경우가 있는지를 어떻게 체크할거냐
3.
체크했을 때, 그 전 상태로 어떻게 되돌아 올거냐
4.
시간 제한을 잘 보자
Sudoku
N-Queen과 마찬가지
백트래킹할 때 중요한 것
1.
어떤 걸 기준으로 순환할거냐
2.
어떤 값을 놓아볼거냐
3.
가능한 경우인지 아닌지를 어떻게 체크하냐
4.
그 전 상태로 어떻게 되돌아 올거냐
