백트래킹

백트래킹

해를 찾는 도중 해가 아니어서 막히면, 돌아가서 다시 해를 찾아가는 기법입니다.

최적화 문제와 결정 문제를 풀때 주로 사용합니다.

 

DFS

가능한 모든 경로를 탑색합니다.

그래서 불필요할 것 같은 경로를 사전에 차단하거나 하는 행동이 없어서 경우의 수를 줄이기 힘듭니다.

그래서 경우의 수를 요구하는 문제는 DFS 로 처리하기 힘들 것입니다.

 

 

 

 

백트래킹

해를 찾아가는 도중, 지금 경로가 해가 될 것 같지 않으면 그 경로를 더 이상가지 않고 되돌아갑니다.

즉, 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

이를 가지치기라고 부릅니다.

 

일반적으로 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들어 효율성이 결정됩니다.

 

정리하자면, 백트래킹이란 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것입니다.