백트래킹(Backtracking)과 DFS(Depth-First Search)

1. 백트래킹? DFS? 백트래킹과 DFS는 어떻게 보면 분리하기가 애매한 개념이다. 굳이 분리해서 의미를 부여하자면 끝까지 가느냐 돌아오느냐로 간단하게 생각해볼 수 있다. DFS 역시 재귀를 통해서 구현하므로 시작 기점으로 돌아오는 개념이 들어가 있기는 하지만, 백트래킹의 경우 현재 가는 길이 더 이상의 해가 아니라고 판단되면 되돌아오는 것을 의미한다. 간단하게 DFS 개념을 정리하자면, 가능한 모든 경로를 깊이 우선으로 탐색하는 것을 의미한다. DFS에 대한 자세한 내용은 아래 게시글을 통해 알아보자! DFS(Depth-First Search) + BFS 복습 깊이 우선 탐색(DFS, Depth-First Search)을 알아보기 이전에 그래프에 대한 개념을 이해해야 하므로, 먼저 아래 포스팅을 참고..

원문링크 : 백트래킹(Backtracking)과 DFS(Depth-First Search)