Search

백트래킹

용도

후보들을 진행하면서 가능성이 없으면 바로 포기하는 방식이다.
탐색하다 왔던길을 돌아가 다른길을 찾는 방식(갔다 왔다 반복한다)
제약 충족 문제(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

참고 자료