[Python] 백트래킹(BackTracking)

1. 백트래킹이란?

백트레킹(BackTracking) 알고리즘

퇴각검색이라고도 불리며 이는 한정조건을 가진 문제를 풀려는 전략이다.

어떤 문제를 푸는데 있어서 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다. 하지만 백트래킹에서는 한정조건에서의 모든 경우의 수를 시도하는 것이기 때문에 상당한 경우의 수들이 배제되어 단순 다중 for문 보다 빠르게 해결되는 경우가 많다.

 

2. 구현 방법

BFS나 DFS와 함께 구현한다.

모든 경우의 수에서 한정조건을 만족하는 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS와 DFS 모두 구현 가능하다.

하지만 백트래킹의 특성에서 한정조건에 부합하지 않다면(Node가 유망하지 않다면) 이전 수행(이전 Node)으로 돌아와야 하기 때문에 BFS보다는 DFS의 구현이 더 편하다. 구현할 때 가장 중요한 것이 한정조건이다.

한정조건을 걸어 완전탐색에서 유망하지 않은 시도를 걸러내는 것이 백트래킹의 본질이다.

 

3. 백트래킹의 한정조건

3*3 행렬 선택 게임



이와 같은 행렬이 존재할 때 3개의 숫자를 선택하는 게임이다.

단, 선택한 숫자들의 행과 열은 모두 중복되면 안된다.

가장 적은 점수를 얻는 것이 승리하는 것이라 할 때, 선택해야하는 숫자 3개를 고르자.

 

먼저, 이 문제를 푸는 가장 쉬운 방법은 모든 방법을 다 해보는 것이다.

숫자 3개를 선택하는 모든 경우를 다 해보는 것이 정답이지만 이 문제에서는 조건이 있다.

 

고른 숫자는 모두 행과 열이 달라야 한다는 것이다. 이것이 바로 한정조건이다.

 

 

 

이 문제를 구조화 하면 이와 같이 나타낼 수 있다.

한정조건과 관계 없이 모든 경우의 수를 나타낸 구조이다.

만약 여기서 한정조건을 추가한다면 아래와 같은 구조가 될 것이다.

 

 

 

 

 

 

---

 

 

 

이와 같이 한정조건을 적용한 뒤에 DFS를 통해 전체 탐색을 진행하는 것이 바로 백트래킹이다.

첫 번째 행에서 만약 1을 선택했다면 두 번째 행의 숫자는 2, 4, 7 중 같은 열인 2를 제외한 4, 7이 유망한 후보가 될 것이다. 따라서 4와 7일 Node에 추가시킨다.

이러한 방식으로 가장 마지막 행까지 모두 수행하면 위와 같은 트리 구조를 얻을 수 있고, 결론적으로 정답을 찾을 수 있다.

 

 

 

 

 

 

---

백트래킹과 DFS의 차이

 

DFS 기본 탐색 구조

 

따라서 백트래킹은 한정조건을 통해서 탐색할 Node가 유망한지 판별하고 유망한 Node만을 추가하여 탐색하는 기법이라고 할 수 있다.

 

백트래킹과 DFS 모두 원하는 값을 찾기 위해서 다양한 방법을 사용하는데 여기에서 차이가 발생한다.

a라는 배열은 [132, 234, 123] 3개의 요소를 가지고 있고 123이라는 값을 찾아야 한다.

 

백트래킹은 불필요한 탐색을 하지 않는다. 순서대로 132라는 값에 접근했을 때 백의 자리 숫자는 1로 동일하지만, 십의 자리 숫자는 2와 다르기 때문에 더이상 탐색을 진행하지 않고 다음 수인 234로 넘어간다.

 

그러나 DFS는 모든 경우의 수를 탐색한다. 132라는 값에 접근했을 때 십의 자리 숫자가 2가 아니더라도 일의 자리까지(트리의 바닥까지) 탐색을 계속한다. 

 

def backtracking(x):
    if 정답이라면:
    	정답 출력
        return 
        
    else: (정답이 아니라면)
    	for 뻗을 수 있는 모든 자식 노드에 대해서:
            if 정답에 유망한 노드라면:
                자식노드로 이동
                backtracking(x+1)
                부모 노드로 이동 (return 후엔 여기가 실행됨)