나름 간단하게? 구현해본 백트래킹 (맞는지는 잘 모르겠으나 어쨋든 백트래킹으로 명명)입니다.
입력받은 배열의 값에 대해서 가능한 모든 순서조합을 만들어냅니다.
단, 모든 순서조합을 위해서는 최초에 배열의 수가 오름차순으로 정렬되어져 있어야 합니다.
최종적인 형태는 내림차순정렬이 되어져 있으며, 이때 함수는 더이상 처리를 하지 않고 들어온 값 그대로 리턴 시켜 버립니다.
내림차순 정렬이 완료 되었으나, 맞는 조합이 없었다면, 해당 문제는 해가 없는 것이 됩니다. (즉, 풀수 없는 문제...)
매번 시도 마다 다음 조합으로 만들어 냅니다. (1차 배열만, 배열의 크기는 무관)
현재 배열의 순서가 답이 될수 없다면, 배열을 다시 백트랙 돌리면 바로 다음 배열 순서의 조합을 만들어냅니다.
1-2-3-4-5-6-7-8-9 의 항이 있었다고 가정할 때...
이 값의 순서가 해당 문제의 답으로서 맞지 않는다면 다음 항으로는
한칸 앞으로 돌아와서(이것이 백트랙이죠)
순서를 바꾸어 볼수 있습니다.
따라서,
1-2-3-4-5-6-7-9-8 을 생각해 볼수 있습니다.
그리고 몇번만 시도를 해보자면...
1-2-3-4-5-6-8-7-9
1-2-3-4-5-6-8-9-7
1-2-3-4-5-6-9-7-8
1-2-3-4-5-6-9-8-7
1-2-3-4-5-7-6-8-9
(...)
9-8-7-6-5-4-3-1-2
9-8-7-6-5-4-3-2-1 (최종값)
예) Array = BackTrack(Array)
(* Array는 1차 배열 변수)
아래 그림은 배열에 현재 값이 {6,7,3,5,4,2,1}이 들어있을 때, 함수 내부에서 다음 배열의 순서인 {6,7,4,1,2,3,5} 로 바뀌는 과정을 설명합니다.
소스코드입니다.
// ===============================================================================================
// BackTrack()
// 제작자 : haebi.kr
// 작성일 : 2010-02-03
// 수 정 : 2010-02-03
// 내 용 : 실행시, 배열에서 모든 나열 방법을 계산하여 매 경우를 순서대로 나열
// 인자로 배열을 넘겨받고, 결과를 배열로 리턴
// 최종적인 형태는 배열의 내림차순 정렬
// ===============================================================================================
private int[] BackTrack(int[] Array)
{
// 백트랙에서 최종적으로 증가된 위치 값을 기억
int BT_LTop = ArrLTop(Array);
// 배열에서 마지막으로 증가한 위치의 값을 기억
int SU_tmp1=0;
// 1. 배열에서 마지막 증가위치가 배열의 끝 일때...
if (BT_LTop == Array.Length - 1)
{
// 마지막 증가위치
Array = ArrSwitch(Array, BT_LTop, BT_LTop - 1);
}
// 2. 마지막 증가위치의 값 바로 앞의 수를 다음 수로 바꾼뒤 뒷부분 정렬
else
{
//마지막 증가값의 위치 앞부분이 -1 이 아닐때...
if (BT_LTop - 1 != -1)
{
// 2-1. 마지막 증가위치 바로 앞의 값을 임시 변수에 저장
SU_tmp1 = Array[BT_LTop - 1];
// 2-2. 마지막 증가위치 바로 앞부분으로 부터 뒷부분 정렬
Array = ArrSort(Array, BT_LTop - 1);
// 2-3. 마지막 증가위치 바로 앞부분부터 뒤로 스캔하여 다음으로 큰값 찾아서 스위칭
Array = ArrSwitch(Array, BT_LTop - 1, ArrNext(Array, BT_LTop - 1, SU_tmp1));
// 2-4. 마지막 증가위치로 부터 뒤로 다시 오름차순 정렬
Array = ArrSort(Array, BT_LTop);
}
else
{
return Array;
}
}
return Array;
}
백트래킹 함수의 소스는 여기까지 입니다만, 이 함수의 내부에서 쓰여진 함수들 또한 별도로 만들어야 합니다.
- ArrLTop()
- ArrSwitch()
- ArrSort()
- ArrNext()
--------------------------------(여기부터 내부에서 쓰인 함수들)------------------------------------------
// ===============================================================================================
// ArrLTop()
// 제작자 : haebi.kr
// 작성일 : 2010-02-03
// 수 정 : 2010-02-03
// 내 용 : 배열에서 마지막으로 값의 변화가 증가된 곳을 리턴
// ===============================================================================================
private int ArrLTop(int[] Array)
{
int i=0;
int LTop=0;
for (i = 0; i < Array.Length - 1; i++)
{
if (Array[i] < Array[i + 1]) // 바로 다음 배열의 값이 현재 값 보다 큰지 체크!
{
LTop = i + 1; // LTop 가장마지막에 이전값과 비교해 증가한 값의 배열 위치 갱신
}
}
return LTop;
}
// ===============================================================================================
// ArrSwitch()
// 제작자 : haebi.kr
// 작성일 : 2010-02-03
// 수 정 : 2010-02-03
// 내 용 : 배열에서 Value1과 Value2의 위치에 있는 값을 교환
// ===============================================================================================
private int[] ArrSwitch(int[] Array, int Value1, int Value2)
{
int tmp;
tmp = Array[Value1];
Array[Value1] = Array[Value2];
Array[Value2] = tmp;
return Array;
}
// ===============================================================================================
// ArrSort()
// 제작자 : haebi.kr
// 작성일 : 2010-02-03
// 수 정 : 2010-02-03
// 내 용 : 배열에서 Pos위치 부터 뒤로 오름차순 정렬
// (버블소트 알고리즘 응용)
// ===============================================================================================
private int[] ArrSort(int[] Array, int Pos)
{
int i = 0;
int j = 0;
int icnt = 0;
// --------------------------------------------------
// 버블소트 알고리즘 (선택범위 정렬)
// --------------------------------------------------
for (i = Pos; i < Array.Length - 1; i++)
{
for (j = Pos; j < Array.Length - 1 - icnt; j++)
{
if (Array[j] > Array[j + 1])
{
Array = ArrSwitch(Array, j, j + 1);
}
}
icnt++;
}
// --------------------------------------------------
return Array;
}
// ===============================================================================================
// ArrNext()
// 제작자 : haebi.kr
// 작성일 : 2010-02-03
// 수 정 : 2010-02-03
// 내 용 : 배열에서 시작위치(stPos)부터 뒤로 스캔하여 입력값(Num)보다 바로 다음으로 큰수를 리턴
// ===============================================================================================
private int ArrNext(int[] Array, int stPos, int Num)
{
int i = 0;
byte detect = 0;
// 입력받은 배열을 tmpArray에 복사
int[] tmpArray = (int[])Array.Clone();
// stPos 으로 부터 뒷부분 정렬
tmpArray = ArrSort(tmpArray, stPos);
for (i = stPos; i < tmpArray.Length; i++)
{
// 바로 같은 값이 발견된 상태이면
if (detect == 1)
{
// 배열에 같은값이 존재 할 경우...
if (tmpArray[i] == Num)
{
detect = 0; // 발견 플래그 초기화
}
else
{
return i; //바로 다음 항목 출력
}
}
// 입력받은값과 배열의 값이 같은경우
if (Num == tmpArray[i])
{
detect++; // 발견 플래그 설정
}
}
return -1;
}
