[algorithm]backtracking

less than 1 minute read

Backtracking

정답을 찾는 도중 정답 아니어서 막히면, 되돌아가서 다시 정답을 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법.


DFS와 Backtracking

  • DFS
    모든경로를 탐색하는 방법. 불필요한 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄이지 못함.
  • Backtracking(가지치기)
    경로를 탐색하는 도중, 정답이 아닌것 같으면 더이상 가지 않고 되돌아감. 반복을 줄일 수 있다.

정리

백트래킹은 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는것.
사용하는 경우: DFS등의 모든 경우의 수를 탐색하는 과정에서 조건문을 걸어 답이 될 수 없는 상황을 정의하고 조건에 부합하면 탐색을 중지하고 다른 경우를 탐색한다.

참고

Updated: