백트래킹

• 모든 경우의 수를 탐색하는 알고리즘
• DFS, BFS이용
• 효율을 위해 탐색하지 않아도 되는곳을 미리 막는 가지치기를 한다.
• 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는것이 좋다.
  • 코딩 테스트에서 이를 고려해 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있음
• 탐색에서 순환이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

<aside> ❗ 백트래킹의 핵심은 가지치기! → 가지치기를 얼마나 잘하느냐가 효율성을 결정한다.

</aside>

어떻게 작성할 것인가?

• 모든 경우의 수를 찾을 수 있도록 코딩
• 특정 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문 작성
• 절대로 답이 될 수 없는 것은 탐색을 종료한다.

N-Queen 문제

→ 길이가 N인 체스판 위에 N개의 퀸이 서로를 공격할 수 없도록 배치할 수 있는 경우의 수는?

1. 백트래킹은 모든 경우의 수를 찾아야 하기에 일단 하고본다.
2. (1,1)에 퀸을 배치
3. 가지치기 : 첫 줄은 더 이상 퀸을 둘 수 없기에 다음 줄 로 이동
4. 가지치기 : 두 번째 줄 첫 칸은 둘 수 없기에 패스
5. 가지치기 : 두 번째 줄 두번째 칸은 둘 수 없기에 패스