[알고리즘] Back tracking (보충)

백트래킹

해를 찾아가는 도중에 지금의 경로가 해가 될 것 같지 않으면, 더 이상 깊이 들어가지 않고, 이전 단계로 다시 돌아가는 알고리즘이다

• 해가 될 만한 가능성이 있으면 유망하다 (Promising)

• 유망하지 않은 노드에 가지 않는 것 (Pruning)
  -> 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드로 돌아가, 다음 자식 노드로 이동한다

순열

• 순열이란?
  어떤 집합의 원소들을 순서대로 배열하는 것

list배열안에 들어있는 원소들의 모든 경우의 수 순열을 구해보자

---

재귀를 사용한 일반 순열

• 원소 1, 2, 3의 모든 경우의 수 순서 조합을 출력할 것이다 (주어진 원소를 모두 나열)

  {1, 2, 3},
  {1, 3, 2},
  {2, 1, 3},
  {2, 3, 1},
  {3, 1, 2},
  {3, 2, 1}

재귀를 사용하여 일반 순열을 탐색하는 방법

1. 깊이별로 원소의 값을 swap한다
2. swap한 조합에서 깊이를 +1 한 뒤 다음 재귀로 호출한다
3. 재귀함수 종료 조건을 만나게 되면 return한 뒤 아래의 반복문에서 아직 수행을 덜 한 원래대로 값을 변경하는 로직을 수행하고 종료
4. 이전 함수로 다시 돌아온다 (백트래킹)

함수의 종료조건이 depth == n 이어도 되고, depth == n -1이어도 가능하다

• n = 3일때 depth도 3이다
• n = 2일때의 swap이 (2,2)이기 때문에, 결국 제자리 swap인것이다

#include <iostream>

using namespace std;

void Permutation(int n, int list[], int depth)
{
	// n - 1이어도 같은 이유
	if (depth == n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << list[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = depth; i < n; i++)
	{
		swap(list[depth], list[i]);
		Permutation(n, list, depth + 1);
		swap(list[i], list[depth]);
	}
}

int main()
{
#pragma region 백트래킹

	int n = 3;
	int element[3] = { 1,2,3 };
	int depth = 0;

	Permutation(n, element, depth);
    
#pragma endregion
	return 0;
}

• 지금 코드가 깊이 우선 탐색을 기반으로 한 코드인 거 같다
  -> 재귀로 계속 깊이를 더 들어간 뒤 해당 함수가 다 완료하면 이전 재귀함수로 돌아가여 다시 재귀함수를 호출하니까, 깊이 먼저 다 탐색하는 깊이 우선 탐색과, 다시 되돌아가는 백트레킹이 합쳐진 듯 하다

• 재귀 함수가 종료되는 순서는 i가 1일때 가장 하위 재귀함수부터 순서대로 종료된다
• 하나씩 종료되가면 i가 3일때의 상위 재귀함수가 마지막으로 종료된다

---

분명 이해는 가는데, 재귀함수로 계속 호출하다보니 헷갈린다
내가 이해한 바로는, 재귀함수를 호출한 뒤 해당 함수가 종료하면 기존의 원소 조합으로 바꾼 뒤 다시 재귀함수를 호출하여 수열을 탐색하는 과정인 거 같다

• 이때 다시 값을 기존의 값으로 변경하여 돌아가는 게 백트래킹인가봄