백트래킹. 대추적..이라고도 한다.
미연시를 생각해보자..
선택지를 고르는 거에 따라 이후 상황이 바뀐다.
즉, 분기가 생긴다..
만약 선택지가 3개가 주어진다면?
상황이 3가지로 나뉜다는 뜻이고,,
이런 선택지를 택하는 횟수가 10번 이라면
3의 10제곱 만큼의 상황이 나뉜다는 것이다.
모든 경우를 다 살펴본다면? 너무 많은 상황을 살펴봐야함.
[보라 머리 여자애] [핑크 머리 여자애]
둘 중에 [보라 머리 여자애]와 친애도를 max 로 찍는게 목표라면?
그것을 위한 선택지를 눌러야됨.
그런데 선택- 선택 - 선택을 잘하다가.. 어떤 선택을 했는데 여기서 친애도가 뚝 떨어졌다면?
그러면 다시 직전 선택으로 돌아와, 다른 선택지로 가야 max를 찍을 수 있음.
이미 친애도가 떨어진 상황에 대한 분기를 더 살펴볼 필요 없음.
기본적으로 모든 경우를 탐색하며, DFS/BFS 둘 다에서 사용할 수 있는 개념임.
대신, 백트래킹을 한다는 건, 가지치기를 통해 탐색의 경우의 수를 줄인다는 것임.
- 최악의 경우, 모든 경우를 다 살펴보게 될 수도 있지만, 가능한 덜 보겠다는 전략
- '가망성이 없으면 굳이 더 가보지 않는다' 는 전략.
백트래킹은 가지치기가 핵심이다.
가지치기를 얼마나 잘하냐에 따라 효율성이 달라진다.
어려운 문제일 수록, 극한의 가지치기를 할 수 있어야함.
cf) 단순히 반복문 여러개해서 break 하는건 백트래킹이 아님.
백트래킹은 탐색 상태를 계속해서 저장하고, 필요시 이전 상태로 되돌아갈 수 있게 코드가 짜져야됨.
ex) 퍼즐풀이, 조합, 최적화문제 (N-Queens, Sudoku 등에 사용)