BackTracking

BackTracking 구조

BackTracking(백트래킹) 알고리즘은 위 그림과 같이 모든 경우의 수를 탐색 할 수 있습니다. 기본적으로 나타낼 숫자의 범위 N과 수열의 길이 M을 입력 받으며 시간복잡도는 O(N*M) 입니다.

 

void backTracking(int dep) {
	int i;
	if (dep >= m) {
		for (i = 0; i < m; i++)
			printf("%d ", arrNum[i]);
		printf("\n");
		return;
	}
	for (i=0;i< n; i++) {
		if (visi[i] == 0) {
			visi[i] = 1;
			arrNum[dep] = i+1;
			backTracking(dep+1);
			visi[i] = 0;
		}
	}
}

1. 매개변수 dep는 수열의 현재 길이를 의미하며 입력받은 M보다 클 경우 현재까지 담은 숫자들을 출력하고 함수를 종료합니다.

2. 반복문으로 i = 0부터 입력받은 N 값 만큼 순회합니다. 이미 방문했던 즉 배열에 담긴 숫자가 아닐때 visi 배열로 방문 체크하고 arrNum 배열에 i 값을 넣은 뒤 재귀함수로 backTracking 함수를 dep + 1 매개변수를 담아 실행합니다.