[알고리즘 이론] 7. 백트래킹

백트래킹

• 제약조건 만족 문제에서 해를 찾기 위한 전략
  • 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(이 후보군은 다시 체크하지 않을 것을 표시) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법
• 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서, 각 루트에 대해 조건이 부합하는지 체크하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버리는 탐색.

알고리즘 문제 추천

1. N과 M(1 ~ 4) (실버 3)

• https://www.acmicpc.net/problem/15649
• https://www.acmicpc.net/problem/15650
• https://www.acmicpc.net/problem/15651
• https://www.acmicpc.net/problem/15652

2. N-Queen (골드 4)

• https://www.acmicpc.net/problem/9663

3. 스도쿠 (골드 4)

• https://www.acmicpc.net/problem/2580

4. 연산자 끼워넣기 (실버 1)

• https://www.acmicpc.net/problem/14888

참고 자료

https://evan-development.tistory.com/147