백트래킹이란?

백트래킹이란 무엇일까? 영어로 해석하면 '뒤로 추적한다?'로 해석이 된다. 저는 백트래킹이라고 하면 '아 DFS로 풀면 되겠구나'라고만 생각했었지 개념에 대해 자세히 알고있거나 정리한 적이 없었다... 그래서 이번 기회에 포스팅을 해보려 한다!

위키백과 정의에 따르면 백트래킹은 일반적인 알고리즘 중 하나로, CSP(Constrain Satisfaction Problems)을 해결하기 위해 쓰인다는 것이다. CSP는 '조건 만족 문제'라는 의미인데 일단 넘어가도록 하겠다. 즉, 백트래킹에 대해 간단히 말하자면 모든 조합의 수를 살펴보는 것이나 단 조건이 만족할 때만 살펴보는 것이다.

백트래킹 (Backtracking) : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

DFS (깊이 우선 탐색)

갑자기 DFS의 개념이 나와 당황했을 수도 있다. 일반적으로 백트래킹은 DFS을 통하여 구현하기 때문에 DFS에 대해서도 간단히 정리하고 넘어가려 한다. DFS는 다음 파트에서 더 자세히 포스팅할 예정이다. (참고로 백트래킹을 BFS로 구현할 경우 상대적으로 많은 메모리가 필요로 하며 탐색 성능이 떨어지기 때문에 DFS을 통하여 구현한다.)

• DFS는 가능한 모든 경로를 탐색한다.

• 답이 되지 않는 경로도 전부 다 탐색하기 때문에 경우의 수가 많아진다. (이는 시간복잡도의 증가로 이어진다!)

Backtracking (백트래킹)

• 백트래킹은 모든 경로를 탐색하지 않는다. 해를 찾아가는 과정에서 지금의 경로가 해가 될 것 같지 않으면 멈추고 전 단계로 되돌아간다. --> 이는 시간복잡도를 줄일 수 있어 효율적으로 해를 찾을 수 있게 된다.
  이렇게 해가 될 것 같지 않으면 멈추고 다른 경로를 탐색하는 것을 가지치기라고 한다. 즉, 불필요한 부분을 쳐내고 올바른 곳으로 최대한 탐색한다는 의미이다.

• 답이 될 만한지 판단한 후 답이 안될 것 같다면 해당 경로의 탐색을 멈추고 가지치기하는 것을 백트래킹이라고 생각하면 된다.

백트래킹의 대표적인 문제로는 N-queen이라는 문제가 있다. 해당 문제를 풀어본다면 백트래킹에 대해 자세히 알 수 있을 것이다.