용도
•
후보들을 진행하면서 가능성이 없으면 바로 포기하는 방식이다.
•
탐색하다 왔던길을 돌아가 다른길을 찾는 방식(갔다 왔다 반복한다)
•
제약 충족 문제(CSP)에 적합(스도쿠, 십자말 풀이, 퍼즐 문제, 문자열 파싱 등)
브루트 포스와 유사?
부루트 포스는 매번 같은 경로를 방문하는데 백트래킹은 가능성이 없으면 포기하기 때문에 더 우아하다.
구현
•
일반적인 백트래킹
public void backtracking(int r, int selectCount, int max) {
if (r == selectCount) {
return;
}
for (int i = 0; i < max; i++) {
if (visited[i]) continue;
list.offer(i);
visited[i] = true;
backtracking(r + 1, selectCount, max);
visited[i] = false;
list.removeLast();
}
}
Java
•
반환값이 존재하는 백트래킹
public int backtracking(int level, int[] cols, int n) {
int sum = 0;
if (level == n) {
return 1;
} else {
for (int i = 0; i < n; i++) {
cols[level] = i;
if (possible(level, cols)) {
sum += backtracking(level + 1, cols, n);
}
}
}
return sum;
}
Java
