백트래킹(Back Tracking)

백트래킹 이란?

완전 탐색을 하던 도중, 현재의 탐색이 무의미한 경우 되돌아가는 알고리즘을 의미한다.

말 그대로 모든 경우의 수에 대해서 탐색을 하던 도중, 조건과 맞지 않을 경우에 대해서는 탐색을 하지 않고 돌아간다는 뜻이다.

 

유명한 문제로 N-Queens 문제가 존재한다.

---

특징

• 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다.
• 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에, 재귀를 사용해야 하는 경우가 많다.
• 조건에 맞지 않는 다면, 이전의 어떤 지점으로 돌아갈 지 정하는 것이 중요하다.
• 가지치기를 어떻게 구성하느냐에 따라 코드의 효율이 달라진다.
• 주로 백트래킹을 구현하다 보면, void함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하는 편이 좋다.

---

가지치기

• 조건에 맞지 않는 부분에 대해 탐색하는 것을 그만둠.
• 이전의 위치로 되돌아간 후에 다시 다른 경로를 탐색함.
• 이를 통해 많은 시간적 이율을 얻을 수 있다.

---

대체 방안

백트래킹 문제는 다른 풀이법으로 문제를 풀 수 있는 경우가 많다.

 

비트마스킹

- 비트(0과 1)의 연산을 활용한 알고리즘.

- 배열의 원소 상태가 2가지로 나뉠 수 있는 백트래킹 문제에서 활용 가능.

- 백트래킹이 아닌 완전탐색이므로 속도는 백트래킹 보다 느림.

 

순열

- 원소의 순서를 정해야 하는 백트래킹 문제에서 활용가능.

- 이 또한 완전탐색이므로 속도는 백트래킹 보다 느림.

---

연관 문제

문제 - 1 페이지