백트래킹 Backtracking
모든 가능한 해를 탐색하는 과정에서 불필요한 경로를 제외하고 최적의 해를 찾는 방법.
DFS + Backtracking
DFS는 단순히 깊이 우선으로 탐색하는 방식이며, 특별한 제약 없이 모든 경로를 탐색.
vs
백트래킹은 탐색 도중 가능성이 없다고 판단되면 그 경로를 버리고 돌아가 다른 경로를 시도.
-> 백트래킹은 DFS와 같이 쓰여서 최적화된 DFS 역할을 할 수 있음. 해를 찾기 위해 비효율적인 경로를 미리 배제하는 추가적인 전략이 적용된 탐색 방식이면 DFS 외에도 다른 탐색과 함께 쓰일 수 있음.
DFS에 visited[node] = false; 이런 문장을 이용해 백트래킹을 적용할 수 있음.
BFS + Backtracking
-> BFS는 한 단계씩 너비를 넓혀가며 탐색하는 방식이지만, 특정 조건을 만족하지 않으면 해당 경로를 더 이상 탐색하지 않도록 가지치기를 적용할 수 있습니다.
Backtracking + Dynamic programming
공통점 : 보통 재귀로 구현
동적 프로그래밍은 복잡한 문제들을 간단한 문제로 분리한 후 작은 문제들을 해결하는 것. 이때 작은 문제들을 계산해 DP 테이블에 저장해서 재사용하는 메모리제이션 기법을 사용할 수 있음.
vs
모든 경우의 수를 살피면서 트리를 순회함. 그러다가 미리 거를 수 있는 후보가 나오면 더 이상 아래로 탐색하지 않고 되돌아가는 것.
-> 메모이제이션을 활용하여 이전에 탐색했던 경로 중 최적이 아닌 경로는 제외하고, 최적의 경로를 찾아가는 과정에서 백트래킹을 적용할 수 있음.
DFS + Backtracking + Dynamic programming
예시 : 백준 1039
dfs 개수가 너무 많을 때 메모이제이션으로 DP에 depth와 값을 저장해놓고 중복 값이 나오면 백트래킹할 수 있음 - 메모이제이션은 dfs/bfs의 경우의 수를 엄청나게 줄일 수 있음
