[Algorithm] Backtracking

Backtracking의 개념에 대해 정리해보도록 하겠습니다.

• 백트래킹이란?
  • 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식. 일종의 트리 탐색 알고리즘.

  • 일반적으로 DFS와 함께 사용합니. 단, DFS를 절대 쓰면 안되는 경우가 있는데, 트리의 깊이가 무한대가 될 때 입니다.

  • 해를 탐색하면서 지금 가고있는 경로가 해가 될 것 같지 않으면, 그 경로를 더이상 가지 않고 이전으로 되돌아가는 방식입니다.
  • 즉 특정한 조건에 부합하는 경우를 찾아가되, 그 조건에 부합하지 않으면 그 경로는 버리고 이전 노드로 돌아가는 방식이라고 이해할 수 있습니다.
• 대표적인 백트래킹 문제로는 N-Queen이 있습니다. 함께 풀어보면 정확히 이해하는데 도움이 될 것 입니다.