Advanced Algorithm - Backtracking

1. 백트래킹이란? 

- 완전탐색 알고리즘의 하나다.  

- 완전탐색을 하는 도중, 현재의 탐색이 무의미하다고 판단이되면 되돌아가는 알고리즘이다. 

- 그래서 퇴각 검색이라 부르기도 한다. 

---

2. 백트래킹의 로직

- 백트래킹은 제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략이다. 

 

• 해를 찾기위해서 어떤 후보군을 대상으로 제약조건을 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단되면, 그 즉시 backtrack(다시는 해당 후보군을 체크하지 않을 것을 표시)한 후, 다른 후보군으로 넘어가는 방식으로 최종적으로 최적의 해를 찾는 전략이다. 
• 백트래킹 전략에 의해 연산의 대상이 되는 후보군이 적어지고, 그만큼 시간복잡도가 줄어드는 것이다. 

 

a) 어떻게 구현하는가? 

1. 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태공간트리(State Space Tree)로 표현한다.

 

2. 구성된 상태공간트리를 DFS 방식으로 탐색하면서 조건에 부합하는지 확인한다. 

▶ a) Promising : 해당 루트(route)가 조건에 맞는지 검사하는 기법 

▶ b) Pruning(가지치기) : 조건에 맞지 않으면 더 이상 탐색하지 않고 다른 루트에서 조건검사를 수행한다. (탐색시간을 절약)

 

* 상태공간트리(State Space Tree)란? 

- 문제해결과정의 중간상태를 각각의 노드로 나타낸 트리

 

상태공간트리의 예시

---

 3. 문제를 통한 백트래킹 로직의 이해 

a) N Queen 문제

- 대표적인 백트래킹 문제 중 하나

- N x N 크기의 체스판에서 N개의 Queen을 서로 공격할 수 없도록 배치하는 문제

- Queen은 다음과 같이 이동할 수 있으므로 배치된 Queen간에 공격할 수 없는 위치로 배치해야 한다. 

 

N Queen 문제

 

b) 어떻게 구현할까 -   Promising & Pruning

- 문제에서 주어진 조건은 2가지 이다.

 - 조건 1) N x N 크기의 체스판에서 N개의 Queen이 존재한다. ex) 4 x 4에서는 4개의 퀸 

 - 조건 2) 서로 공격할 수 없어야 한다. 

 

- 만약 4x4 크기의 체스판이 있다고 생각해보자.(아래 사진참고) 

- Queen은 수평, 수직, 대각선으로 공격(이동)할 수 있다. 이 조건을 하나씩 생각해보자. 

 

1) 수평

- 수평으로 움직이는 Queen의 공격을 피하기 위해서, 한 행에는 1개의 Queen만 위치할 수 있다. 

 

2) 수직

- 수직으로 움직이는 Queen의공격을 피하기 위해서, 열이 겹치만 안된다. 

 

 

3) 대각선

- 행과 열이 겹치지 않는 조건에서 대각의 공격을 피하기 위해서, 아래 그림의 하얀색 박스에 위치해야 한다.  

 

- 첫번째 Queen의 위치에 의해, 두번째 Queen은 (1,3)에만 위치할 수 있다는 것을 알 수 있다. 

 

 

- 이 과정을 계속해서 거치다보면 다음과 같은 결과를 도출할 수 있다. 

 

- 최종적으로 모든 조건을 만족하는 결과가 나올 때까지, 위의 과정을 (0,0)부터 수행하여 최적의 답을 찾는 방법이다.  

 

 

---

4. 백트래킹을 이용한 N Queen 문제 코드구현 

# is_available() - 수직, 수평, 대각선 조건을 판단하기 위한 함수
def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):    
        if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row:
            return False
    return True
        


# N(체스판 크기), current_row(현재 행)
# current_candidate(조건을 만족하여 배치된 queen의 위치)
# final_result(최종적으로 배치된 모든 queen의 위치)
def DFS(N, current_row, current_candidate, final_result):
    # 현재 행이 N과 같다면 지금까지 배치된 결과가 모두 조건을 만족함
    if current_row == N:
        final_result.append(current_candidate[:])
        return
    
    # 하나의 행마다 N개의 열을 검증하기 위한 for문
    for candidate_col in range(N):
        # is_available() - 수직, 수평, 대각선 조건을 판단하기 위한 함수
        if is_available(current_candidate, candidate_col): #조건을 만족한다면
            current_candidate.append(candidate_col)
            DFS(N, current_row + 1, current_candidate, final_result)#재귀함수
            # 조건을 만족하지 못한 경우, pop하여 제거 및 다음 열로 넘어가기
            current_candidate.pop()


def solve_n_queens(N):
    final_result = []
    DFS(N, 0, [], final_result)
    return final_result    

 

 

[테스트 결과]

 

-결과에 대한 해석은 다음과 같이 하면된다.

 

ex) [1,3,0,2]

- 첫번째 행은 1번자리 = (0,1)

- 두번째 행은 3번자리 = (1,3)

- 세번째 행은 0번자리 = (2,0)

- 네번째 행은 2번자리 = (3,2)