백트래킹 알고리즘

일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용할 수 있습니다.
백트래킹의 일반화된 형식은 DFS입니다.
DFS는 일반적으로 완전 탐색이라고 불리는, 모든 경우의 수를 확인하는 방법이며 재귀함수 이용해 구현합니다.

백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 완전 탐색이 아니라 조건이 맞지 않게 되면 이전 단계로 되돌아가서 해를 찾아들어가는 기법입니다.

백트래킹의 일반적인 코드 형태입니다.

function recursive() {
  if 종료 조건 만족한다면 {
    처리
  }

  for 자식 노드를 하나씩 확인하며 {
    if 임의의 조건을 만족한다면 {
      자식 노드 방문 처리
      재귀 함수 호출
      자식 노드 방문 처리 해제
    }
  }
}