백트래킹21 백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3. 이전 1 2 3 다음
