백트래킹 (Backtracking)

---

백트래킹 (Backtracking)

** 아래 포스팅 내용 관련하여, 더 나은 방법이나 아이디어가 있으신 경우에는 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

백트래킹(Backtracking)의 특징

 

 백트래킹은 말 그대로 '역추적'을 의미합니다. 문제 해결을 위한 모든 경우의 수를 따져보기 위해서 (완전 검색 (Exhaustive search), 실제로 모든 케이스를 다 직접 확인한다는 의미는 아니지만) 일반적으로 활용되는 기법 중 하나입니다. 

 백트래킹은 우선 어떤 하나의 가능한 케이스를 확인하고, 가능하지 않다면 다시 Back하고, 다시 다른 가능성있는 케이스를 확인하면서 Solution이 도출될 때까지 이런 과정이 계속적으로 반복되도록 구현하게 됩니다. 따라서 일반적으로 백트래킹은 알고리즘의 구조 특성상 재귀함수를 사용하여 구현됩니다.

 백트래킹에 있어 중요한 것은 문제의 요구사항에 따라서, 구현된 알고리즘의 연산량이 제한 시간을 넘어버리게 되는 경우가 발생한다는 것입니다. PC의 성능이 매우 뛰어나서 아무런 속도의 제약없이 모든 케이스를 단순 반복 검색으로 하나씩 확인할 수 있으면 좋겠지만, 아직까지는 Hardware의 제약 사항으로 인하여, 무작정 전 검색을 수행하는 데에는 한계가 발생할 수 밖에 없습니다. 따라서, 더 이상 탐색할 필요가 없는 후보군에 대해서는 재귀 호출을 더 이상 하지 않고 가지치기 (Pruning 또는 Branch and bound) 하는 것이 매우 중요합니다. 굳이 체크할 필요가 없다고 판단되는 후보군들을 적절히 제외시켜서, 연산 시간은 줄이면서 완전 검색이 수행되도록 하는 것이 백트래킹의 핵심이라고 할 수 있겠습니다.

백트래킹 알고리즘의 Pseudo code

BOOL complete_flag = false;

BOOL Backtracking( input1 arr[], input2 depth, input3 data )
{
	int i;

	// Check whether this combination is the solution or not.
	if (IsComplete(arr, depth, data))
	{
		FinalProcess();		// Go the final process.
		complete_flag = true;	// Finish.
	}
	else
	{
		int num_of_next_targets = 0;
		temp_input next_targets[MAX_NUM];

		// Increase the count of depth.
		depth++;

		// Update the list of next targets and the number.
		FindNextTargets(arr, depth, data, next_targets, &num_of_next_targets);

		// Check every feasible target.
		for (i = 0; i < num_of_next_targets; i++)
		{
			arr[depth] = next_targets[i];
			Backtracking(arr, depth, data);

			// If finished, every function is return '0' and closed.
			if (complete_flag) return 0;
		}
	}
}

     Backtracking은 앞서 말씀드린 것처럼 재귀함수로 구현되어 있습니다.

• IsComplete
   현재의 input array의 조합이 solution이 될 수 있는지를 확인합니다. solution은 한가지일 수도 있고, 여러가지 일 수도 있는데, 문제의 요구 사항에 맞게 수정하는 것이 중요합니다. 만약 문제의 solution이 한가지라면 complete_flag를 활용해서 모든 backtracking을 종료할 수도 있습니다. 
  
  
• FinalProcess
   만약 solution에 해당될 경우 요구사항에 맞게 필요한 최종 operation을 수행하게 됩니다.
  

• FindNextTarget
   현재 depth에서 후보군이 될 수 있는 target input을 update합니다. 현재까지의 조합된 input array가 필요할 수도 있고 없을 수도 있습니다. 현재 depth에서 해당 target number만큼 backtracking을 수행하게 됩니다.

• depth
   현재 input array의 위치를 나타냅니다. 즉, depth가 추가될 때마다 탐색의 깊이가 점점 깊어지는 것을 의미합니다,

예제 : 부분 집합 구하기

 부분 집합을 구하는 문제를 통해서, backtracking에 대한 적용을 연습해보도록 하겠습니다. N개 (1 <= N <= 100)의 원소가 입력으로 주어지고, 해당 수들로 조합 가능한 모든 부분집합을 찾아봅니다. 

• IsComplete 
   여기서는 현재의 input array의 depth가 최종 깊이인지를 확인하게 됩니다. input argument 중 data는 입력된 수의 max를 전달합니다. IsComplete로 결정될 solution이 한가지가 아닌 case이므로, complete_flag는 여기서는 사용되지 않습니다.
  
  
• FinalProcess
   만약 solution에 해당될 경우 요구사항에 맞게 필요한 최종 operation을 수행하게 됩니다. 여기서는 현재 조합의 부분집합을 출력합니다. 0일 경우, 현재 집합에서 해당 숫자는 포함하지 않고 1일 때만 포함하는 것으로 출력합니다.
  

• FindNextTarget
   현재 depth에서 후보군이 될 수 있는 target input을 update합니다. 해당 위치의 숫자가 포함될지 말지의 두가지 경우가 있습니다. 이 문제의 경우 이전 input array의 정보가 현재 target 후보군 설정에 영향을 주지 않는 case가 되겠습니다.

   구현할 경우, 다음 예제와 같습니다.

예제 : 부분 집합 구하기 - Source code

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM (100)

typedef enum {
	FALSE = 0,
	TRUE = 1
}BOOL;

int g_test_input_arr[MAX_NUM];
int g_max_input_num = 0;

BOOL complete_flag = FALSE;

BOOL IsComplete( char *input, int depth, int data )
{
	if (depth == (data - 1))	return TRUE;
	else				return FALSE;
}

void FinalProcess( char arr[] )
{
	int i;
	printf("{");
	for (i = 0; i < g_max_input_num; i++)
	{
		if (arr[i] == 1)
		{
			printf("%5d", g_test_input_arr[i]);
		}
	}
	printf(" }\n");
}

void FindNextTargets( char arr[], int depth, int data, char *next_targets, int *num_of_next_targets )
{
	next_targets[0] = 0;
	next_targets[1] = 1;

	*num_of_next_targets = 2;
}

BOOL Backtracking( char arr[], int depth, int data )
{
	int i;

	// Check whether this combination is the solution or not.
	if (IsComplete(arr, depth, data))
	{
		FinalProcess( arr );		// Go the final process.
		//complete_flag = TRUE;	// Finish.
	}
	else
	{
		int num_of_next_targets = 0;
		char next_targets[MAX_NUM];

		// Increase the count of depth.
		depth++;

		// Update the list of next targets and the number.
		FindNextTargets(arr, depth, data, next_targets, &num_of_next_targets);

		// Check every feasible target.
		for (i = 0; i < num_of_next_targets; i++)
		{
			arr[depth] = next_targets[i];
			Backtracking(arr, depth, data);

			// If finished, every function is return '0' and closed.
			//if (complete_flag) return TRUE;
		}
	}
}

int main(void)
{
	int i;
	char *backtrack_arr;

	scanf("%d", &g_max_input_num);

	backtrack_arr = (char *)malloc(sizeof(char) * g_max_input_num);

	for (i = 0; i < g_max_input_num; i++)
	{
		scanf("%d", &(g_test_input_arr[i]));
	}

	for (i = 0; i < 2; i++)
	{
		backtrack_arr[0] = i;
		Backtracking(backtrack_arr, 0, g_max_input_num);
	}

	free(backtrack_arr);
}

  

예제 : 부분 집합 구하기 - 출력 결과

 

조금 더 복잡한 backtracking 적용 예시에 대해 궁금하신 분들은, 아래에 소개된 N-queen문제 관련 posting을 참고하시기 바랍니다.

출처 / 관련 링크

- N queen : http://jayce-with.tistory.com/17

- 숫자판 점프 : http://jayce-with.tistory.com/19

- 좋은 수열 : http://jayce-with.tistory.com/18