[컴퓨터 알고리즘] 백트래킹 알고리즘

백트래킹 알고리즘

---

• 반복문을 통해 어떤 해를 찾는 과정을 반복하다가, 더 이상 해가 될 수 없는 경우가 없다고 판단되면 뒤로 돌아가 다른 경우를 재탐색 하는 알고리즘을 의미한다.

 

DFS와 백트래킹의 차이점

---

DFS 알고리즘

• 깊이 우선 탐색 알고리즘으로, 모든 가능한 경우의 수를 탐색하는 알고리즘이다.
• 일단 되고 안되고 간에 모든 경우를 탐색하기 때문에, 어떤 조건을 넣어서 탐색 자체를 끊고 돌아갈 수 없다.

백트래킹

• DFS와 유사하게 recursive하게 코드가 돌아가며 경우의 수를 찾다가, 더 해봐도 경우의 수가 존재하지 않을 거라는 확신이 들면 (분기가 걸리면) 끊어버리고 이전으로 돌아가 다음의 경우의 수를 찾는 알고리즘이다.
• 이때 당연히 중요한 것은 "이 분기가 걸리는 타이밍"을 정확히 판단해 코드로 작성해주는 것이다.

 

아래의 링크는 위의 백트래킹 알고리즘을 사용해 푼 Silver와 Gold 수준의 문제이다.

https://baekjoon-deeplearning.tistory.com/52

백준 15654 - N과 M (5) [C/C++]

https://baekjoon-deeplearning.tistory.com/27

백준 9019 - DSLR [C/C++] 백트래킹 알고리즘