백트래킹, 브루트 포스, DFS의 차이점?

위의 세 가지 모두 경우의 수를 다 돌려보는 느낌이 들지만, 정확히 따지자면 다음과 같다고 합니다.

 

백트래킹

이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법입니다.

반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로는 DFS와 연관이 깊다고 합니다.

브루트 포스

꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 기법입니다.

DFS

여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가야만 DFS라고 합니다.