백트래킹 알고리즘이란?

조건을 만족하는 해를 구할 때, 조건에 맞는 해가 아니라면 이전으로 돌아가 만족하는 해를 찾는 과정을 반복하는 알고리즘.

DFS와 백트래킹의 차이

• DFS : 가능한 모든 경로를 탐색.
• 백트래킹 : 정해진 조건에 해당하는 경로만 탐색.
  -> 가능한 조건을 체크하며 탐색하기 때문에 DFS보다 우수한 성능을 보임.

백트래킹 예시

3X3 행렬 선택 게임

1 2 3
4 5 6
7 8 9
핸드폰 키패드와 비슷한 행렬에서 3개의 숫자를 선택하는데, 단 선택한 숫자들의 행과 열은 모두 중복되면 안된다. 3개의 숫자 중 가장 큰 숫자는?

DFS로 구현한다면
1-4-7-8-9-5-7-8 ... 3-6-7-8-9
의 순서대로 순회를 할테지만

주어진 조건에서 행과 열은 모두 중복되지 않아야 하는 조건이 있다.
따라서 백트래킹으로 구현한다면
1-4(조건에 만족x)-5-7-8(조건에 만족x)-9...3-5-8(조건에 만족x)-9
의 순서대로 순회를 한다.

참고
https://velog.io/@gayeong39/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BackTracking