[알고리즘,개념] Backtracking

Backtracking

• 정의 : 모든 조합의 수(경우의 수)를 살펴본다. 단, 특정 조건이 만족할 때(Promising)만, 그 조합을 본다. - "the algorithm design manual" (1997.스티븐 스키에나)
• 모든 경우의 수를 찾는 것보다, 경우에 따라, 훨씬 빠를 수 있다(pruning). 
• Promising,Pruning(가지치기) 기법을 이용한다.
• Promising: 해당 루트가 조건에 맞는지를 검사하는 기법.
• Pruning : 조건에 맞지 않으면, 포기하고, 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법.

 

 

너무나도 유명한 예제 중 하나인, N-Queen 문제를 살펴보면서, Promising의 개념이 뭔지, Pruning의 개념이 뭔지 구체화 시켜보자. 

 

N-Queen

N*N 크기의 체스판에 N개의 퀸을 서로 공격 할 수 없도록 배치하는 문제이다.

• 퀸은 상,하,좌,우,대각선(8방향)으로 자유롭게 움직일 수 있는 체스말이다.

가볍게, 4*4의 보드에, 4개의 퀸을 서로 공격 할 수 없도록 배치해보자.

퀸을 (0,0)부터 순서대로 하나씩 배치하다보면, 자연스럽게 알 수 있는 것이 있다. 퀸을 한 개를 놓으면, 그 퀸의 움직임 때문에, 자동적으로 놓을 수 없는 공간이 정해진다. 퀸의 움직임이 바로 backtracking 할 때, Promising, 특정 조건이라고 할 수 있다. 

 

예를들어, (0,0)에 놓는다면, 다음 퀸을 놓을 수 있는 자리는 파란색인 곳일 거다.

그렇다면, 퀸 한개를 놓고, 그 퀸과 같은 행/열/대각선에 놓는 경우는 다 볼 필요도 없다.(Pruning 가지치기)

위와 같이, 퀸을 놓을 수 있는 자리를 생각하다보면, (0,0)으로 시작되는건 안된다는걸 단 4번만에 알 수 있게 된다. (와우)

이런 방법으로, Queen을 다시, 백지에서 (0,1)에도 놓아보고.. 이런식으로 진행을 하는게 Backtracking이다.

의사코드로 생각한다면 , 아래와 같게 될거다.

def promising(y):
	if 같은 행 : return false
	if 같은 열 : return false
    if 같은 대각선: return false
   return True
def backtracking(y):
	if y==n:
    		ans+=1
        	return
	if promise(y):
    		visited[y]=True
    		backtracking(y+1)
            visited[x]=False

backtracking(0)
print(ans)

 

위의 로직이 핵심적인 N-Queen의 로직인건 확실하다. 하지만, 여기서 조금 더 욕심을 내보자! 위의 코드도 핵심 로직을 다 담고있다.

 

메모리 쪽으로도, 최적화를 위해서, 2차원 board에서 직접 가능한지 아닌지, 기록하는것이 아닌,

1차원 배열의 index => 2차원 배열의 row, 1차원 배열의 value => 2차원 배열의 col으로 생각해줄 수 있다.

왜냐하면, 1행에 퀸은 오직 1개만 놓을 수 있기 때문이다.

 

무슨 소리냐하면,  아래의 배치는, 공격하지 않게되는 배치 중 하나인 경우인데,  (1,2),(2,4),(3,1),(4,3) 에 위치하게 되는데, 이걸 1차원 배열로 나타내기 위해서, arr[0] =2,arr[1] =4,arr[2]=1,arr[3]=3 처럼, arr[y]=x로 나타낼 수 있음!

(1,2) ,(2,4),(3,1),(4,3)에 각각 위치한다.

N=int(input())
count=0
board=[0]*15

def dfs(depth):
    global count
    if depth==N:
        count+=1
        return
    for i in range(N):
        board[depth]=i
        if promise(depth):
            dfs(depth+1)
            
def promise(x):
    for i in range(x):
        if board[x]==board[i]: #같은 열에 있다면 , return False
            return False
        elif abs(board[x]-board[i])==x-i: # 두 좌표의 차이가 같으면, 같은 대각선에 있음.(기울기)
            return False
    return True

dfs(0)
print(count)

 

Backtracking이 된 이유도 자연스럽게 와닿는다.

어떤 상태가 내가 찾는 답이 될 만한지 판단한 후,  유망하지 않다고 결정되면 그 노드의 이전(부모)상태로 돌아가(Backtracking) 다음(자식)상태 노드로 가는 과정을 반복하게 됩니다.

답 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 루트에 가지 않는 것을 가지치기(pruning).

일종의 최적화를 하는거다.