Backtracking(되추적) 개념

Backtracking 개념

 

주어진 문제를 트리(State Space Tree)로 어떻게 표현할지, 문제에 맞는 유망성검사(Promising function)는 어떻게 구성할지 설계상의 고민이 끝났다면 어떻게 코드로 나타내고 구현할지 코드상의 고민이 필요하다.

 

코드구현상의 고민

1. 트리의 묵시적 표현과 어떤 자료구조로 대체할 것인가?

트리는 우리가 구현할 알고리즘의 흐름을 파악하기 위한 용도이기 때문에 반드시 구현할 필요는 없다. 또한, 트리로 구현하지 않는다면 어떠한 자료구조로 대체하여 방문과 되추적을 표현할 것인가도 고민해줘야 한다.

 

예시

예를들어보자. 4-Queens Problem (4개의 Queen들을 서로 위협이 되지 않게 4 X 4 행렬에 배치하는 문제)의 SST는 다음과 같을 것이다. 어떤 자료구조로 대체할 수 있을까?

 

 

 

 

1) 2차원배열

가장먼저 생각나는건 2차원 배열일 것이다. 위 트리의 (0행,1열)노드 방문은 곧, arr[0][1] = 1 로 표현할 수 있을 것이다. 마찬가지로 (1행,3열)노드 방문은  arr[1][3] = 1로 표현할 수 있다. 

 

 

 

 

2) 1차원배열

하지만, 2차원배열은 크기에 따른 메모리초과의 문제도 있을 수 있고 현재 문제에선 sparse matrix 즉 낭비가 있는 2차원배열 형태이기 때문에 다른 자료구조로 고민해볼 수도 있다. 위의 2차원 배열의 특징은 각 행의 퀸의 위치가 하나만 있는 즉, 특정행과 특정열로 퀸의 위치를 표시할 수 있다는 것이다. 그렇다면 배열의 index: 행, element: 열로 나타낼 수 있다. 

 

 

 

 

이 경우 방문과 되추적의 의미는 아래와 같다. 

board[0] = 0;  (0행, 0열)노드 방문

board[0] = 1;  되추적하여 (0행, 1열)노드 방문

board[0] = 2;  되추적하여 (0행, 2열)노드 방문

 

 

이처럼 트리를 어떤 자료구조로 대체할 것인지 그 경우 방문과 되추적은 어떻게 표현이 되는지를 생각해내는 것이 중요하고 아직 연습이 더 필요한 부분이라고 생각된다.

 

 

 

2. Recursive function의 Base Case고려

트리탐색은 재귀적인 함수호출로 이루어지기 때문에 재귀의 종료지점인 base case를 반드시 명시해줘야 한다. 우리가 묵시적으로 표현한 트리에서 알고리즘 흐름상 어느지점에서 탐색이 종료되고 되추적이 일어나는지 파악하여 조건식을 구상해야할 것이다.