Backtracking

 

개요

모든 경우의 수를 탐색하는 Brute Force 알고리즘으로 조건이 존재할 때 사용한다.

State-Space Tree 라고도 한다.

기본적으로 DFS 를 사용하며 조건에 부합하지 않는 branch에 대해 Pruning (가지치기)를 하여 불필요한 경우의 수를 따지지 않는다.

 

 

Branch and Bound 

BFS 베이스로 (depth == level) 기준으로 자리를 구분한다.

 

---

관련 문제

www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Write a program to print all permutations of a given string - GeeksforGeeks

 

풀이

DFS version

---

BFS version

set_difference라고 차집합을 구하는 함수가 있는데 

요놈이 정렬된 집합 혹은 set 자료구조에 대해서만 빠짐없이 원소의 차집합을 구하는 것을 알게되었다.

그래서 루프 도중에 현재까지 모아온 문자열을 정렬하는 로직이 추가된다.

테스트 케이스 문자열 길이가 짧기때문에 별 문제가 되진 않았다.

진짜 개 빡친다. ㅋㅋ 

 

---

Reference

압둘바리 만세..

www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/