만재송

백트래킹 기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다' 는데 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동한다. DFS 의 장점은 무한히 깊은곳을 찾아야할때 효과적이다. 하지만 DFS 는 모든곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법이다. 가지치기를 얼..