백트래킹

음. bfs 보다는 좀 난이도가 있긴하지만... 생각하기가.. 하지만 비슷한 몇문제를 풀어보면, 이해가 되고... 코딩은 짧습니다. 재귀함수의 일반적인 특징처럼요. 백트래킹의 일반적인 자세한 설명은 위키피디아 잘되있네요.  간단하게 요약 설명하면. 백트래킹은 모든 경우에 수를 찾아보는 겁니다.  그리고 코딩할때는 재귀함수로 구현을 많이 하구요. 다른 알고리즘에 비해 시간이 많이 걸릴 경우가 많음으로 최적화 같은 작업이 필요할 때도 있습니다. 어떤 사람은 가지치기라고도 합니다. 즉, 아래 같은 깊이 우선 탐색을 진행하는데 더이상 밑으로 내려가거나, 옆으로 이동하지 않아도 될 경우가 있을때는 그 가지는 해볼 필요가 없음으로 버린다는 개념입니다.

  비교적 설명이 간단한 이진트리를 예를 들면 아래 그림에서 부분집합의 모든 경우를 탐색 해보는 겁니다.

 글로써 순서대로 설명 하면 아무것도 선택안한 상태 0에서 출발, 1을 포함 하냐 안하냐. 그다음 2를 포함하냐 안하냐, 그다음 3을 포함하냐 안하냐 가지고 트리를 쭉 만들어 가면 모든 부분 집합의 경우의 수를 탐색한겁니다. 즉 원소의 개수가 3개임으로 8개의 경우가 나오겠지요. 2^3 개..

  이렇게 탐색할때에는 dfs가 주로 사용됩니다. 이유는 위키의 그림에서 보면 알수 있습니다. 아래 그림입니다.

  그런데 위키에서도 설명되었듯이. 백트래킹은 모든 경우의 수를 탐색하는것이기에 다른 알고리즘 보다 시간이 오래 걸립니다. 그래서 최적화가 필요한 문제들이 있습니다. 최적화는 앞에서 설명했듯이 가지치기라고도 하는데. 이진 트리에서 설명하면 부분 집합의 합으로 2라는 숫자를 만드라고 했다면.. 합이 2이상 넘는 가지 부터는 더이상 검색하지 않도록 하는 겁니다.  앞에 설명했던 이진트리에서는 아래 가지들을 잘라 내는 거죠..

 가지치기가 원소가 얼마 안된 상태라 그렇지.. 트리가 크다면 속도에 엄청난 개선이 있을 겁니다.   백트래킹은 재귀 함수 설계만 하면 거의 문제 해결됬다고 볼 수 있습니다. 초콜렛 공장 문제로 한 번 설계하는 과정을 생각 해보면

1. void Dfs(int count, int sum) //선택한 종류, 돈의 총합을 인자로..
2. {
3. if (sum >= money) return; //입력 받은 돈보다 크거나 같을 경우에는 함수종료
4. if (count >= selCnt) return;//입력받은 선택 개수보다 큰경우에도 함수 종료
6. for (int i = 0; i < chocoTotalkind; i++) //입력 받은 종류들을 하나씩 선택 해본다..
7. {
8. sel[i]++; //선택한 종류를 기록한다.. 25개 넘는지 체크도 해야하고, 답.. 즉 포장된 초콜렛의 종류를 카운트하기 위해 필요.
9. if (sel[i]>MAX_SEL) //25개이상 선택 될 경우에는 더 추가하면 안된다.
10. {
11. sel[i]--;
12. continue;
13. }
14. count++; //파라미터로 받은 개수에서 한개더 선택한다.
15. sum += cost[i];//선택했음으로 돈의 합도 업데이트한다.
17. Dfs(count, sum); //추가된 개수와, 돈을 파라미터로 dfs를 다시 호출한다. // 이함수가 빠져나오는 조건은 함수 맨위 두줄 이다.
18. int curkindcnt = kindcnt();
19. if (maxkindcnt < curkindcnt)
20. maxkindcnt = curkindcnt;//함수가 빠져나왔다면 개수를 체크하고, 선택한 max 종류를 업데이트한다.
22. count--; // dfs 함수가 호출되기 직전의 상태로 되돌린다.
23. sel[i]--;// dfs 함수가 호출되기 직전의 상태로 되돌린다.
24. sum -= cost[i];// dfs 함수가 호출되기 직전의 상태로 되돌린다.
25. }

1.  파라미터 인자로 선택한 종류와 돈의 총합을 주고 있습니다.  선택한 개수와 돈의 제약이 있음으로 하나씩 더 선택해가면 over되지 않는지 체크하기 위해 필요 한 인자들입니다.
2. 3,4번 줄에서는 종료 조건입니다. 물론 over되었을때는 리턴됨으로 가지치기라고 볼수도 있습니다.
3. 가장 중요한 부분인 상태 업데이트(8,14,15번), 재귀함수호출(17), 상태원복(22,23,24) 입니다.

백트래킹은 대부분 위의 구조를 가집니다.  특히 상태 업데이트, 재귀함수 호출, 상태원복이런 구조로 짜여질 수 밖에 없습니다. 왜냐 하면 모든 경우를 탐색해야 하기 때문에 포함해서도 해보고, 포함 안해서도 해봐야 하기 때문이죠.. 백트래킹은 항상 저런 구조를 가지고 있음으로, 문제를 보고 아이거 백트래킹인데 하는 감이 온다면..ㅎ 저런 구조를 기억해내고, 맞춰 보면 될거 같습니다.