백트래킹
-
[알고리즘] 백트래킹STUDY/Algorithm 2021. 3. 17. 12:01
백트래킹 백트래킹이란, 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다. 백트래킹의 목적은 해가 될 조건을 만족시키는 "진짜 해"를 효율적으로 찾는것이 백트래킹의 목적이다. 백트래킹은 탐색을 진행하다가 더 갈 수 없게되면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었고, 주로 재귀적으로 구현한다. '모든 해'란, 예를 들어 탈출로가 두개인 미로 문제를 생각해보자. 이러한 미로에서 탈출할 수 있는 최단 경로는 2개가 존재한다. 이 2개 해를 일컬어 '모든 해'라고 한다. '후보 해' 란, 해가 될 수 있는 가능성을 가진 부분해의 조합이다. 백트래킹은 DFS를 빼고 이야기 할 수 없는 알고리즘이다. DFS는 백트래킹의 골격을 이루는 알고리즘이다. 백트래킹은 DFS 방식으로..