백트래킹 알고리즘 (Backtracking Algorithm)

백트래킹(backtracking)은 한정 조건을 가진 문제를 풀려는 전략이다.

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다.

이런 문제는 변수 집합으로 이루어지는데, 한정 조건을 구성하기 위해서 각각의 변수들은 값이 있어야 한다.

백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다.

이것이 가지는 장점은  많은 부분의 조합을 배제(가지치기)하는 것이다. 이로 인해 풀이 시간이 단축된다.

 

예를 통해서 백트래킹을 알아 보도록 하자. 

가장 쉽게 접할 수 있는 예시로는 4-Queens Problem이 있다.

 

N-Queens Problem은 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 만들기 위해서는 백트래킹 알고리즘이 필요하다.

 

4 * 4를 기준으로 문제를 풀어보자. 

 

빨간색 선이 퀸이 이동할 수 있는 경로이고, 첫번째 퀸과 공격할 수 없게 배치하기 위해서는 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다. 첫번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다.

 

만약 이 문제를 가지치기 하지않는 DFS 알고리즘으로 풀이했다면 유망하지 않은 (2, 1), (2, 2) 지점도 검사했을 것이다. 그렇게되면 더 큰 체스판에서 퀸을 놓는 경우의 수를 찾을 때 수많은 연산이 일어나게 된다.

 

이제 (2, 3)에 퀸을 놓는다. 그리고 유망한 노드를 검사해보면 다음과 같다.

 

그러면 3행에 Queen을 놓을 수 있는 곳이 없다. 이를 그림으로 표현하면 다음과 같다.

 

이 경우 (2, 3)은 유망한 자식이 하나도 없으므로 더이상 유망하다고 하지 않는다.

그렇기 때문에 (2, 3)이 아닌 (2, 4)에 Queen을 넣어보자. 그러면 다음과 같을것이다.

 

그림으로 표현하면 다음과 같다.

 

이제 유망한 자식의 값 (3, 2)에 Queen을 넣어보자. 

 

그러면 다음과 같이 (3, 2) 자식 노드 중에는 유망한 자식이 없다.

 

고로 더이상 Queen을 놓을 수가 없게 되었다. 그렇다면 부모로 돌아가 다음 유망한 자식한테 간다.

 

그래서 (1, 1)는 유망하지 않으므로  유망한 자식인 (1, 2)에 Queen을 놓는다.

이런식으로 반복하다보면 다음과 같은 결과가 나오게 된다.

 

이처럼 백트래킹 해답을 찾는 과정에서 유망한지 즉, 해답이 될 가능성이 있는지를 확인하고 유망하지 않다면, 더이상 깊게 들어가지 않고 부모 노드로 돌아오는 방식을 취한다.

 

단순히 이 작업을 DFS로 했을 경우 검색해야 하는 노드의 갯수는 

1개(Root) + 4개(1행) + 16개(2행) + 64(3행) + 256(4행) 중에서 155번째 노드를 검색하다 해답을 발견하게 된다.

 

하지만 백트래킹을 사용하면 27번의 노드검색만으로 해답을 찾게된다.

 

결과적으로 백트래킹 알고리즘은 단순 DFS에 비해 효율을 몇배나 끌어올릴수 있다.